{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T17:55:10Z","timestamp":1769968510581,"version":"3.49.0"},"reference-count":82,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"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":4580,"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":[[2001,1]]},"DOI":"10.1016\/s0304-3975(00)00285-1","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T10:59:17Z","timestamp":1027594757000},"page":"1-166","source":"Crossref","is-referenced-by-count":90,"title":["L(A)=L(B)? decidability results from complete formal systems"],"prefix":"10.1016","volume":"251","author":[{"given":"G\u00e9raud","family":"S\u00e9nizergues","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(00)00285-1_BIB1","series-title":"Handbook of Forma Languages","article-title":"Context-free languages","author":"Autebert","year":"1996"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB2","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/174130.174141","article-title":"Decidability of bisimulation equivalence for processes generating context-free languages","volume":"40","author":"Baeten","year":"1993","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB3","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF01692060","article-title":"Graph expressions and graph rewritings","volume":"20","author":"Bauderon","year":"1987","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0304-3975(76)90049-9","article-title":"An improvement on Valiant's decision procedure for equivalence of deterministic finite-turn pushdown automata","volume":"3","author":"Beeri","year":"1976","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB5","series-title":"String Rewriting Systems Texts and Monographs in Computer Science","author":"Book","year":"1993"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB6","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(00)00285-1_BIB7","doi-asserted-by":"crossref","unstructured":"C. Choffrut, A generalization of Ginsburg and Rose's characterisation of gsm mappings, Proc. ICALP 79, Lecture Notes in Computer Science, Springer, 1979, pp. 88\u2013103.","DOI":"10.1007\/3-540-09510-1_8"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB8","doi-asserted-by":"crossref","unstructured":"N. Chomsky, Three models for the description of a language, Symp. on Information Theory; IRE Trans. Inform. Theory IT-2 (1956).","DOI":"10.1109\/TIT.1956.1056813"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB9","unstructured":"N. Chomsky, Context-free grammars and pushdown storage, Tech. Report no. 65, Research Laboratory of Electronics, Massachusetts Institute of Technology, 1962."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB10","series-title":"Computer Programming and Formal Systems","first-page":"118","article-title":"The algebraic theory of context-free languages","author":"Chomsky","year":"1963"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB11","series-title":"Regular Algebra and Finite Machines","author":"Conway","year":"1971"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB12","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0304-3975(78)90008-7","article-title":"A representation of trees by languages, I","volume":"6","author":"Courcelle","year":"1978","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB13","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0304-3975(78)90039-7","article-title":"A representation of trees by languages, II","volume":"7","author":"Courcelle","year":"1978","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB14","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF01744577","article-title":"An axiomatic approach to the Korenjac\u2013Hopcroft algorithms","author":"Courcelle","year":"1983","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB15","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(83)90059-2","article-title":"Fundamental properties of infinite trees","volume":"25","author":"Courcelle","year":"1983","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB16","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF02088013","article-title":"The monadic second-order logic of graphs II: infinite graphs of bounded width","volume":"21","author":"Courcelle","year":"1989","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB17","doi-asserted-by":"crossref","unstructured":"B. Courcelle, Graph rewriting: and algebraic and logic approach, in: J. van Leeuwan (Ed.), Handbook of Theoretical Computer Science, vol. B, 1990, pp. 193\u2013242.","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB18","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0168-0072(90)90027-Y","article-title":"The monadic second-order logic of graphs IV: Definability properties of equational graphs","volume":"49","author":"Courcelle","year":"1990","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB19","first-page":"461","article-title":"Recursive applicative program schemes","author":"Courcelle","year":"1990"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB20","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/BF00288472","article-title":"Synchronizable deterministic pushdown automata and the decidability of their equivalence","volume":"23","author":"Culik II","year":"1986","journal-title":"Acta Inform."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB21","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(82)90009-3","article-title":"The IO- and OI-hierarchies","volume":"20","author":"Damm","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB22","doi-asserted-by":"crossref","unstructured":"J. Engelfriet, Iterated pushdown automata and complexity classes, Proc. 15th STOC 1983 (365\u2013373).","DOI":"10.1145\/800061.808767"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB23","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0304-3975(86)90052-6","article-title":"Pushdown machines for the macro tree transducer","volume":"42","author":"Engelfriet","year":"1986","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB24","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1016\/S0022-0000(77)80019-6","article-title":"Equivalence problems for deterministic context-free languages and monadic recursion schemes","volume":"14","author":"Friedman","year":"1977","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"10.1016\/S0304-3975(00)00285-1_BIB25","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0211013","article-title":"A polynomial algorithm for deciding the equivalence problem for 2-tape deterministic finite state acceptors","volume":"11","author":"Friedman","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB26","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0304-3975(81)90055-4","article-title":"Dpda's in \u2018atomic normal form\u2019 and applications to equivalence problems","volume":"14","author":"Gallier","year":"1981","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"10.1016\/S0304-3975(00)00285-1_BIB27","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1137\/0213047","article-title":"n-rational algebras I. Basic properties and free algebras","volume":"13","author":"Gallier","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB28","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0022-0000(73)80040-6","article-title":"Program schemes, recursion schemes, and formal languages","volume":"7","author":"Garland","year":"1973","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB29","first-page":"620","volume":"Inform. Control","author":"Ginsburg","year":"1966","journal-title":"Deterministic context-free languages"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB30","first-page":"350","volume":"J. Assoc. Comput. Mach.","author":"Ginsburg","year":"1961","journal-title":"Two families of languages related to ALGOL"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB31","unstructured":"L.G. Haines, Generation and recognition of formal languages, Ph.D. Thesis, Massachusetts Institute of Technology, 1965."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB32","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/0304-3975(91)90356-7","article-title":"The equivalence problem of multitape finite automata","volume":"78","author":"Harju","year":"1991","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB33","series-title":"Introduction to Formal Language Theory","author":"Harrison","year":"1978"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB34","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."},{"issue":"1\u20132","key":"10.1016\/S0304-3975(00)00285-1_BIB35","first-page":"142","article-title":"A polynomial algorithm for deciding bisimilarity of normed context-free processes","volume":"158","author":"Hirshfeld","year":"1996","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB36","first-page":"82","article-title":"The logical schemes of algorithms","volume":"1","author":"Ianov","year":"1960","journal-title":"Problems Cybernet. (USSR)"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB37","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0020-0190(81)90116-2","article-title":"On the decidability of equivalence problem for deterministic pushdown transducers","volume":"13","author":"Ibarra","year":"1981","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB38","doi-asserted-by":"crossref","unstructured":"P. Jancar, Bisimulation is decidable for one-counter processes, Proc. ICALP 97, Springer, Berlin, 1997, pp. 549\u2013559.","DOI":"10.1007\/3-540-63165-8_210"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB39","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/S0022-0000(69)80027-9","article-title":"Regular expressions and the equivalence of programs","volume":"3","author":"Kaplan","year":"1969","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB40","doi-asserted-by":"crossref","unstructured":"A.J. Korenjac, J.E. Hopcroft, Simple deterministic languages, Proc. 7th Annu. IEEE Switching and Automata Theory Conf., 1966, pp. 36\u201346.","DOI":"10.1109\/SWAT.1966.22"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB41","series-title":"Automata Studies","first-page":"3","article-title":"Representation of events in nerve sets and finite automata","author":"Kleene","year":"1956"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB42","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/S0019-9958(65)90426-2","article-title":"On the translation of languages from left to right","volume":"8","author":"Knuth","year":"1965","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB43","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(00)00285-1_BIB44","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/S0022-0000(70)80022-8","article-title":"On formalised computer programs","volume":"4","author":"Luckham","year":"1970","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB45","unstructured":"A.N. Maslov, Multilevel stack automata, Problemi Peredachi Inform. (1976) 55\u201362."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB46","unstructured":"Y.V. Matiyasevich, personal communication, 1995."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB47","doi-asserted-by":"crossref","unstructured":"Y.V. Meitus, The equivalence problem for real-time strict deterministic pushdown automata, Kibernetika 5 (1989) 14\u201325 (English translation in Cybernet. Systems Anal. (1990) 581\u2013594) (in Russian).","DOI":"10.1007\/BF01075213"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB48","doi-asserted-by":"crossref","unstructured":"Y.V. Meitus, Decidability of the equivalence problem for deterministic pushdown automata, Kibernetika 5 (1992) 20\u201345 (English translation in Cybernet. Systems Anal. (1993) 672\u2013690) (in Russian).","DOI":"10.1007\/BF01131845"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB49","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0022-0000(70)80021-6","article-title":"Equivalences on program schemes","volume":"4","author":"Milner","year":"1970","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB50","article-title":"Report on the algorithmic language Algol60","volume":"3","author":"Naur","year":"1960","journal-title":"Comm. ACM"},{"issue":"2","key":"10.1016\/S0304-3975(00)00285-1_BIB51","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0022-0000(82)90044-7","article-title":"The equivalence problem for LL- and LR-regular grammars","volume":"24","author":"Nijholt","year":"1982","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB52","series-title":"On the Interpretation of Recursive Polyadic Program Schemes, Symposia Mathematica, vol. 15","author":"Nivat","year":"1975"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB53","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0022-0000(87)90017-1","article-title":"On deciding the confluence of a finite string-rewriting system on a given congruence class","volume":"35","author":"Otto","year":"1987","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB54","unstructured":"M. Oyamaguchi, Some results on Equivalence and Subclass Containment Problems for DPDA's, Proc. 5th IBM Symp. on Mathematical Foundations of Computer Science, 1980, p. 35."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB55","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1145\/28869.28881","article-title":"The equivalence problem for real-time d.p.d.a's","volume":"34","author":"Oyamaguchi","year":"1987","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB56","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/S0019-9958(80)90887-6","article-title":"The equivalence problem for real-time strict deterministic languages","volume":"45","author":"Oyamaguchi","year":"1980","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB57","unstructured":"M.S. Paterson, Equivalence problems in a model of computation, Ph.D. Thesis, University of Cambridge, England, 1967."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB58","series-title":"Theory of Recursive Functions and Effective Calculability, Mc Graw-Hill: Series in Higher Mathematics","author":"Rogers","year":"1967"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB59","unstructured":"V.Yu. Romanovskii, Equivalence problem for real-time strict deterministic pd-automata, Kibernetika (5) (1980) 49\u201359 (English translation in Cybernet. Systems Anal. (1981) 689\u2013700."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB60","doi-asserted-by":"crossref","unstructured":"V.Yu. Romanovskii, Equivalence problem for real-time deterministic pushdown automata, Kibernetika (2) (1986) 13\u201323 (English translation in Cybernet. Systems Anal. (1986) 162\u2013175).","DOI":"10.1007\/BF01074776"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB61","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1016\/S0022-0000(75)80057-2","article-title":"Program equivalence and context-free grammars","volume":"11","author":"Rosen","year":"1975","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB62","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1016\/S0019-9958(70)90446-8","article-title":"Properties of deterministic topdown grammars","volume":"17","author":"Rosenkrantz","year":"1970","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB63","doi-asserted-by":"crossref","unstructured":"J. Rutledge, On Ianov's program schemata, J. Assoc. Comput. Mach. 1964 (1\u20139).","DOI":"10.1145\/321203.321204"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB64","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1016\/S0019-9958(63)90306-1","article-title":"On context-free languages and push-down automata","volume":"6","author":"Schutzenberger","year":"1963","journal-title":"Inform. and Control"},{"issue":"3","key":"10.1016\/S0304-3975(00)00285-1_BIB65","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0890-5401(89)90032-1","article-title":"Church\u2013Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages","volume":"81","author":"S\u00e9nizergues","year":"1989","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB66","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0304-3975(90)90048-M","article-title":"Some decision problems about controlled rewriting systems","volume":"71","author":"S\u00e9nizergues","year":"1990","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB67","first-page":"75","article-title":"Formal languages and word-rewriting","volume":"vol. 909","author":"S\u00e9nizergues","year":"1994"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB68","unstructured":"G. S\u00e9nizergues, \u0393(A) \u223c \u0393(B)? Tech. Rep. no. 1183-97, LaBRI, Universit\u00e9 Bordeaux I, can be accessed at URL, http:\/\/www.labri.u-bordeaux.fr\/\u223cges\/, 1997."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB69","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, vol. 9, URL: http:\/\/www.elsevier.nl\/locate\/entcs\/volume9.html, 1997.","DOI":"10.1016\/S1571-0661(05)80430-X"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB70","unstructured":"G. S\u00e9nizergues, L(A)=L(B)? Tech. Rep. no. 1161-97, LaBRI, Universit\u00e9 Bordeaux I, can be accessed at URL, http:\/\/www.labri.u-bordeaux.fr\/, 1997."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB71","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues, The equivalence problem for deterministic pushdown automata is decidable, 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(00)00285-1_BIB72","series-title":"Proc. FOCS\u201998","first-page":"120","article-title":"Decidability of bisimulation equivalence for equational graphs of finite out-degree","author":"S\u00e9nizergues","year":"1998"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB73","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0304-3975(97)00145-X","article-title":"A polynomial algorithm testing partial confluence of basic semi-Thue systems","volume":"192","author":"S\u00e9nizergues","year":"1998","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB74","unstructured":"G. S\u00e9nizergues, T(A)=T(B)?, Proc. ICALP 99, Lecture Notes in Computer Science, vol. 1644, Springer, Berlin, 1999, pp. 665\u2013675, Full proofs in Technical Report 1209-99 of LaBRI, T(A)=T(B)?, pp. 1\u201361."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB75","doi-asserted-by":"crossref","unstructured":"C. Stirling, Decidability of bisimulation equivalence for normed pushdown processes, Proc. CONCUR 96, Lecture Notes in Computer Science, vol. 1119, Springer, Berlin, 1996, pp. 217\u2013232.","DOI":"10.1007\/3-540-61604-7_57"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB76","doi-asserted-by":"crossref","unstructured":"C. Stirling, Decidability of dpda's equivalence, Tech. Rep., Edinburgh ECS-LFCS-99-411, 1999, pp. 1\u201325, Theoret. Comput. Sci., submitted.","DOI":"10.1145\/333623.333624"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB77","doi-asserted-by":"crossref","unstructured":"E. Tomita, K. Seino, A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict, Theoret. Comput. Sci. (1989) 39\u201353.","DOI":"10.1016\/0304-3975(89)90096-0"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB78","unstructured":"L.G. Valiant, Decision procedures for families of deterministic pushdown automata, Ph.D. Thesis, University of Warwick, 1973."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB79","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0019-9958(74)90839-0","article-title":"The equivalence problem for deterministic finite-turn pushdown automata","volume":"25","author":"Valiant","year":"1974","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(00)00285-1_BIB80","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1016\/S0022-0000(75)80005-5","article-title":"Deterministic one-counter automata","volume":"10","author":"Valiant","year":"1975","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(00)00285-1_BIB81","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(00)00285-1_BIB82","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. Intelligence"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500002851?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500002851?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T04:48:37Z","timestamp":1578458917000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397500002851"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":82,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["S0304397500002851"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(00)00285-1","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}