{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,7]],"date-time":"2024-12-07T05:04:22Z","timestamp":1733547862114,"version":"3.30.1"},"reference-count":30,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4946,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2000,1]]},"DOI":"10.1016\/s0304-3975(99)00106-1","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T00:48:18Z","timestamp":1027644498000},"page":"309-334","source":"Crossref","is-referenced-by-count":7,"title":["Complete formal systems for equivalence problems"],"prefix":"10.1016","volume":"231","author":[{"given":"G\u00e9raud","family":"S\u00e9nizergues","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(99)00106-1_BIB1","series-title":"Handbook of Formal Languages","article-title":"Context-free languages","author":"Autebert","year":"1996"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB2","doi-asserted-by":"crossref","unstructured":"J. Baeten, J. Bergstra, J. Klop, Decidability of bisimulation equivalence for processes generating context-free languages, in Proceedings of PARLE 87, Lecture Notes in Computer Science, vol. 259, Springer, Berlin, 1987, pp. 94\u2013111.","DOI":"10.1007\/3-540-17945-3_5"},{"year":"1988","series-title":"Rational Series and their Languages","author":"Berstel","key":"10.1016\/S0304-3975(99)00106-1_BIB3"},{"issue":"1","key":"10.1016\/S0304-3975(99)00106-1_BIB4","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1051\/ita\/1993270100231","article-title":"A fast algorithm to decide on the equivalence of stateless dpda","volume":"27","author":"Caucal","year":"1993","journal-title":"RAIRO Theoret. Inform. Appl."},{"key":"10.1016\/S0304-3975(99)00106-1_BIB5","unstructured":"D. Caucal, Bisimulation of context-free grammars and of pushdown automata, in: Modal Logic and Process Algebra, CSLI Lectures Notes, vol. 53, 1995, pp. 85\u2013106."},{"key":"10.1016\/S0304-3975(99)00106-1_BIB6","article-title":"Une forme canonique pour les grammaires simples d\u00e9terministes","volume":"1974","author":"Courcelle","journal-title":"RAIRO informatique"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB7","article-title":"An axiomatic approach to the Korenjac\u2013Hopcroft algorithms","volume":"1983","author":"Courcelle","journal-title":"Math. Systems theory"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB8","doi-asserted-by":"crossref","unstructured":"J. Engelfriet, Iterated pushdown automata and complexity classes, in: Proc. 15th STOC, 1983, pp. 365\u2013373.","DOI":"10.1145\/800061.808767"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB9","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0304-3975(86)90052-6","article-title":"H. Vogler, Pushdown machines for the macro tree transducer","volume":"42","author":"Engelfriet","year":"1986","journal-title":"Theoret. Comput. Sci."},{"year":"1978","series-title":"Introduction to Formal Language Theory","author":"Harrison","key":"10.1016\/S0304-3975(99)00106-1_BIB10"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB11","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0304-3975(79)90024-0","article-title":"On equivalence of grammars through transformation trees","volume":"9","author":"Harrison","year":"1979","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(99)00106-1_BIB12","doi-asserted-by":"crossref","unstructured":"Y. Hirshfeld, M. Jerrum, F. Moller, A polynomial algorithm for deciding bisimilarity of normed context-free processes, in Proceedings of Dagstuhl seminar on Algorithms in Automata theory, Theoret. Comput. Sci., 1996, to appear.","DOI":"10.1016\/0304-3975(95)00064-X"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB13","doi-asserted-by":"crossref","unstructured":"J.E. Hopcroft, A.J. Korenjac, Simple deterministic languages, in: Proceedings Seventh Annual IEEE Switching and Automata Theory Conference, 1966, pp. 36\u201346.","DOI":"10.1109\/SWAT.1966.22"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB14","series-title":"Proceedings ICALP 97","first-page":"549","article-title":"Bisimulation is decidable for one-counter processes","author":"Jancar","year":"1997"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB15","series-title":"Handbook of Forma Languages","first-page":"609","article-title":"Semirings and formal power series","author":"Kuich","year":"1996"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB16","unstructured":"A.N. Maslov, Multilevel stack automata, Problemi Peredachi Informatsii, 1976, pp. 55\u201362."},{"key":"10.1016\/S0304-3975(99)00106-1_BIB17","unstructured":"Y.V. Meitus, The equivalence problem for real-time strict deterministic pushdown automata, Kibernetika 5 (in Russian) (1989) 14\u201325, English translation in Cybernet. Systems Anal. (1990) 581\u2013594."},{"year":"1989","series-title":"Communication and Concurrency","author":"Milner","key":"10.1016\/S0304-3975(99)00106-1_BIB18"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB19","doi-asserted-by":"crossref","unstructured":"D. Park, Concurrency and Automata on Infinite Sequences, Lecture Notes in Computer Science, vol. 104, Springer, Berlin, 1981, pp. 167\u2013183.","DOI":"10.1007\/BFb0017309"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB20","unstructured":"G. S\u00e9nizergues, \u0393(A) \u223c \u0393(B)?, Technical Report, nr1183-97, LaBRI, Universit\u00e9 Bordeaux I, can be accessed at URL, http:\/\/www.labri.u-bordeaux.fr\/\u223cges\/, 1997, pp. 1\u2013112."},{"key":"10.1016\/S0304-3975(99)00106-1_BIB21","unstructured":"G. S\u00e9nizergues, L(A) = L(B)?, Technical Report, nr1161-97, LaBRI, Universit\u00e9 Bordeaux I, can be accessed at URL, http:\/\/www.labri.u-bordeaux.fr\/, 1997, pp. 1\u201371."},{"key":"10.1016\/S0304-3975(99)00106-1_BIB22","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues,L(A) = L(B)?, in: Proc. INFINITY 97, pp. 1\u201326, Electronic Notes in Theoretical Computer Science 9, URL: http:\/\/www.elsevier.nl\/locate\/entcs\/vol.9.html, 1997.","DOI":"10.1016\/S1571-0661(05)80430-X"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB23","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues, The equivalence problem for deterministic pushdown automata is decidable, in: Proc. ICALP 97, Lecture Notes in Computer Science, vol. 1256, Springer, Berlin, 1997, pp. 671\u2013681.","DOI":"10.1007\/3-540-63165-8_221"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB24","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues, Decidability of bisimulation equivalence for equational graphs of finite out-degree, in: Rajeev Motwani (eds.), Proceedings FOCS\u201998, pp. 120\u2013129. IEEE Computer Society Press, 1998. Full proofs in technical report 1183-97 of LaBRI, \u0393 (A) \u223c \u0393 (B)?, pp. 1\u2013113.","DOI":"10.1109\/SFCS.1998.743435"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB25","unstructured":"G. S\u00e9nizergues, L(A) = L(B)?, Technical Report, LaBRI, Universit\u00e9 Bordeaux I, 1998, Corrected and extended version of report 1161-97; can be accessed at URL, http:\/\/www.labri.u-bordeaux.fr\/\u223cges\/; pp. 1\u2013166; Theoret. Comput. Sci., submitted for publication."},{"key":"10.1016\/S0304-3975(99)00106-1_BIB26","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues, The equivalence problem for deterministic pushdown transducers into abelian groups, in: L. Brim, J. Gruska, and J. Zlatuska (ed.), Proceedings MFCS\u201998, volume 1450, pp. 305\u2013315. Lecture Notes in Computer Science, 1998.","DOI":"10.1007\/BFb0055780"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB27","doi-asserted-by":"crossref","unstructured":"C. Stirling, Decidability of bisimulation equivalence for normed pushdown processes, in: Proc. CONCUR 96, Lecture Notes in Computer Science, vol. 1119, Springer, Berlin, 1996, pp. 217\u2013232","DOI":"10.1007\/3-540-61604-7_57"},{"year":"1973","series-title":"Decision procedures for families of deterministic pushdown automata, Ph. D. Thesis","author":"Valiant","key":"10.1016\/S0304-3975(99)00106-1_BIB28"},{"key":"10.1016\/S0304-3975(99)00106-1_BIB29","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF01704910","article-title":"Iterated linear control and iterated one-turn pushdowns","volume":"19","author":"Vogler","year":"1986","journal-title":"Math. Systems Theory"},{"issue":"4","key":"10.1016\/S0304-3975(99)00106-1_BIB30","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1111\/j.1467-8640.1994.tb00007.x","article-title":"Linear iterated pushdowns","volume":"10","author":"Weir","year":"1994","journal-title":"Comput. Intell."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599001061?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599001061?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T05:52:06Z","timestamp":1733464326000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397599001061"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["S0304397599001061"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(99)00106-1","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}