{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T05:18:18Z","timestamp":1737609498678,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":75,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540421214"},{"type":"electronic","value":"9783540451327"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45132-3_7","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T17:00:06Z","timestamp":1194973206000},"page":"114-132","source":"Crossref","is-referenced-by-count":2,"title":["Some Applications of the Decidability of DPDA\u2019s Equivalence"],"prefix":"10.1007","author":[{"given":"G\u00e9raud","family":"S\u00e9nizergues","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,5,9]]},"reference":[{"issue":"2","key":"7_CR1","first-page":"243","volume":"35","author":"J.M. Autebert","year":"1987","unstructured":"J.M. Autebert, L. Boasson, and G. S\u00e9nizergues. Groups and NTS languages. JCSS vol.35, no2, pages 243\u2013267, 1987.","journal-title":"JCSS"},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/174147.169807","volume":"40","author":"S. Arnborg","year":"1993","unstructured":"S. Arnborg, B. Courcelle, A. Proskurowski, and D. Seese. An algebraic theory of graph reduction. J. ACM 40, pages 1134\u20131164, 1993.","journal-title":"J. ACM"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0304-3975(92)90011-4","volume":"103","author":"M. Bauderon","year":"1992","unstructured":"M. Bauderon. Infinite hypergraph II, systems of recursive equations. TCS 103, pages 165\u2013190, 1992.","journal-title":"TCS"},{"key":"7_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/3-540-17945-3_5","volume-title":"Proceedings of PARLE 87","author":"J. Baeten","year":"1987","unstructured":"J. Baeten, J. Bergstra, and J. Klop. Decidability of bisimulation equivalence for processes generating context-free languages. In Proceedings of PARLE 87, pages 94\u2013111. LNCS 259, 1987."},{"key":"7_CR5","unstructured":"A. Blumensath and E. Gr\u00e4edel. Automatic structures. In Proceedings LICS, pages 105\u2013118. IEEE Computer Society Press, 2000."},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"R.V. Book and F. Otto. String Rewriting Systems.Texts and monographs in Computer Science. Springer-Verlag, 1993.","DOI":"10.1007\/978-1-4613-9771-7"},{"key":"7_CR7","series-title":"Lect Notes Comput Sci","first-page":"3","volume-title":"Proceedings 1rst ICALP","author":"P. Butzbach","year":"1973","unstructured":"P. Butzbach. Une famille de congruences de Thue pour lesquelles L\u2019\u00e9quivalence est d\u2019ecidable. In Proceedings 1rst ICALP, pages 3\u201312. LNCS, 1973."},{"issue":"4","key":"7_CR8","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1051\/ita\/1990240403391","volume":"24","author":"D. Caucal","year":"1990","unstructured":"D. Caucal. Graphes canoniques des graphes alg\u00e9briques. RAIRO, Informatique Th\u00e9orique et Applications, 24(4), pages 339\u2013352, 1990.","journal-title":"RAIRO, Informatique Th\u00e9orique et Applications"},{"key":"7_CR9","unstructured":"D. Caucal. Bisimulation of context-free grammars and of pushdown automata. In Modal Logic and process algebra, pages 85\u2013106. CSLI Lectures Notes, vol. 53, 1995."},{"key":"7_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/3-540-57208-2_11","volume-title":"Bisimulation is decidable for basic parallel processes","author":"S. Christensen","year":"1993","unstructured":"S. Christensen, Y. Hirshfeld, and F. Moller. Bisimulation is decidable for basic parallel processes. LNCS 715, Springer, pages 143\u2013157, 1993."},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1006\/inco.1995.1129","volume":"121","author":"S. Christensen","year":"1995","unstructured":"S. Christensen, H. H\u00fcttel, and C. Stirling. Bisimulation equivalence is decidable for all context-free processes. Information and Computation 121, pages 143\u2013148, 1995.","journal-title":"Information and Computation"},{"key":"7_CR12","unstructured":"Y. Cochet. Sur l\u2019alg\u00e9bricit\u00e9 des classes de certaines congruences d\u00e9finies sur le monoide libre. Th\u00e8se de l\u2019universit\u00e9 de Rennes, 1971."},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(78)90008-7","volume":"6","author":"B. Courcelle","year":"1978","unstructured":"B. Courcelle. A representation of trees by languages,I. Theoretical Computer Science 6, pages 255\u2013279, 1978.","journal-title":"Theoretical Computer Science"},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0304-3975(78)90039-7","volume":"7","author":"B. Courcelle","year":"1978","unstructured":"B. Courcelle. A representation of trees by languages,II. Theoretical Computer Science 7, pages 25\u201355, 1978.","journal-title":"Theoretical Computer Science"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(83)90059-2","volume":"25","author":"B. Courcelle","year":"1983","unstructured":"B. Courcelle. Fundamental properties of infinite trees. Theoretical Computer Science 25, pages 95\u2013169, 1983.","journal-title":"Theoretical Computer Science"},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF02088013","volume":"21","author":"B. Courcelle","year":"1989","unstructured":"B. Courcelle. The monadic second-order logic of graphs ii: infinite graphs of bounded width. Math. Systems Theory 21, pages 187\u2013221, 1989.","journal-title":"Math. Systems Theory"},{"key":"7_CR17","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0168-0072(90)90027-Y","volume":"49","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle. The monadic second-order logic of graphs iv: definability properties of equational graphs. Annals of Pure and Applied Logic 49, pages 193\u2013255, 1990.","journal-title":"Annals of Pure and Applied Logic"},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"B. Courcelle. Recursive applicative program schemes. In Handbook of Theoretical Computer Science, edited by J. Van Leeuwen, pages 461\u2013490. Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88074-1.50014-7"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"A. Carbone and S. Semmes. A graphic apology for symmetry and implicitness. Preprint, 1999.","DOI":"10.1093\/oso\/9780198507291.001.0001"},{"key":"7_CR20","first-page":"243","volume":"B","author":"N. Dershowitz","year":"1991","unstructured":"N. Dershowitz and J.P. Jouannaud. Rewrite systems. In Handbook of theoretical computer science, vol.B, Chapter 2, pages 243\u2013320. Elsevier, 1991.","journal-title":"Handbook of theoretical computer science Chapter 2"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"D.B.A. Epstein, J.W. Cannon, D.F. Holt, S.V.F. Levy, M.S. Paterson, and W.P. Thurston. Word processing in groups. Jones and Bartlett, 1992.","DOI":"10.1201\/9781439865699"},{"key":"7_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1007\/3-540-58131-6_41","volume-title":"Important Results and Trends in Theoretical Computer Science, (Colloquium in honor of Aarto Salomaa)","author":"J. Engelfriet","year":"1994","unstructured":"J. Engelfriet. Deciding the NTS-property of context-free grammars. In Important Results and Trends in Theoretical Computer Science, (Colloquium in honor of Aarto Salomaa), pages 124\u2013130. Springer-Verlag,LNCS nr 812, 1994."},{"key":"7_CR23","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1016\/S0022-0000(77)80019-6","volume":"14","author":"E.P. Friedman","year":"1977","unstructured":"E.P. Friedman. Equivalence problems for deterministic context-free languages and monadic recursion schemes. Journal of Computer and System Sciences 14, pages 344\u2013359, 1977.","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR24","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0304-3975(81)90055-4","volume":"14","author":"J.H. Gallier","year":"1981","unstructured":"J.H. Gallier. Dpda\u2019s in\u2019 atomic normal form\u2019 and applications to equivalence problems. Theoretical Computer Science 14, pages 155\u2013186, 1981.","journal-title":"Theoretical Computer Science"},{"key":"7_CR25","doi-asserted-by":"crossref","unstructured":"S. Ginsburg and S. Greibach. Deterministic context-free languages. Information and Control, pages 620\u2013648, 1966.","DOI":"10.1016\/S0019-9958(66)80019-0"},{"key":"7_CR26","first-page":"1","volume":"1","author":"P. Grosset-Grange","year":"1993","unstructured":"P. Grosset-Grange. D\u00e9cidabilit\u00e9 de la confluence partielle d\u2019un syst\u00e8me semi-Thu\u00e9ien rationnel. M\u00e9moire de DEA de l\u2019universit\u00e9 de Bordeaux 1, pages 1\u201321, 1993.","journal-title":"M\u00e9moire de DEA de l\u2019universit\u00e9 de Bordeaux"},{"key":"7_CR27","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1006\/inco.1994.1101","volume":"115","author":"J. Groote","year":"1994","unstructured":"J. Groote and H. H\u00fcttel. Undecidable equivalences for basic process algebra. Information and Computation 115, pages 354\u2013371, 1994.","journal-title":"Information and Computation"},{"key":"7_CR28","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0022-0000(73)80040-6","volume":"7","author":"S.J. Garland","year":"1973","unstructured":"S.J. Garland and D.C. Luckham. Program schemes, recursion schemes, and formal languages. Journal of Computer and System Sciences 7, pages 119\u2013160, 1973.","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR29","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-10284-1","volume-title":"Algebraic Semantics","author":"I. Guessarian","year":"1981","unstructured":"I. Guessarian. Algebraic Semantics. Lecture Notes in Computer Science, vol. 99, 1981."},{"key":"7_CR30","doi-asserted-by":"crossref","unstructured":"Y. Hirshfeld, M. Jerrum, and F. Moller. A polynomial algorithm for deciding equivalence of normed context-free processes. In Proceedings of FOCS\u201994, pages 623\u2013631. IEEE, 1994.","DOI":"10.1109\/SFCS.1994.365729"},{"key":"7_CR31","doi-asserted-by":"crossref","unstructured":"H. H\u00fcttel and C. Stirling. Actions speak louder than words: Proving bisimilarity for context-free processes. In LICS\u201991, pages 376\u2013385. IEEE, 1991.","DOI":"10.1109\/LICS.1991.151661"},{"key":"7_CR32","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1145\/322217.322230","volume":"27","author":"G. Huet","year":"1980","unstructured":"G. Huet. Confluent reductions: abstract properties and applications to term rewriting systems. JACM vol. 27 no 4, pages 797\u2013821, 1980.","journal-title":"JACM"},{"key":"7_CR33","first-page":"82","volume":"1","author":"I.I. Ianov","year":"1960","unstructured":"I.I. Ianov. The logical schemes of algorithms. Problems of Cybernetics (USSR) 1, pages 82\u2013140, 1960.","journal-title":"Problems of Cybernetics (USSR)"},{"key":"7_CR34","doi-asserted-by":"crossref","unstructured":"P. Jancar. Bisimulation is decidable for one-counter processes. In Proceedings ICALP 97, pages 549\u2013559. Springer Verlag, 1997.","DOI":"10.1007\/3-540-63165-8_210"},{"key":"7_CR35","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/S0022-0000(69)80027-9","volume":"3","author":"D.M. Kaplan","year":"1969","unstructured":"D.M. Kaplan. Regular expressions and the equivalence of programs. Journal of Computer and Systems Sciences 3, pages 361\u2013386, 1969.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"7_CR36","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/3-540-60178-3_93","volume":"94","author":"B. Khoussainov","year":"1995","unstructured":"B. Khoussainov and A. Nerode. Automatic presentations of structures. In Logic and Computational Complexity, Indianapolis,94, pages 367\u2013392. L.N.C.S nr 960, 1995.","journal-title":"Logic and Computational Complexity, Indianapolis"},{"key":"7_CR37","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/S0022-0000(70)80022-8","volume":"4","author":"D.C. Luckham","year":"1970","unstructured":"D.C. Luckham, D.M. Park, and M.S. Paterson. On formalised computer programs. Journal of Computer and Systems Sciences 4, pages 220\u2013249, 1970.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"7_CR38","doi-asserted-by":"crossref","unstructured":"O. Ly. Automatic graphs and D0L-sequences of finite graphs. Preprint, submitted to JCSS, pages 1\u201333, 2000.","DOI":"10.1007\/3-540-44612-5_49"},{"key":"7_CR39","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1007\/3-540-44612-5_49","volume-title":"Proceedings MFCS\u20192000","author":"O. Ly","year":"2000","unstructured":"O. Ly. Automatic graphs and graph D0L-systems. In Proceedings MFCS\u20192000, pages 539\u2013548. Springer, LNCS No 1893, 2000."},{"key":"7_CR40","unstructured":"Y.V. Matiyasevich. Personal communication. 1995."},{"key":"7_CR41","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0022-0000(70)80021-6","volume":"4","author":"R. Milner","year":"1970","unstructured":"R. Milner. Equivalences on program schemes. Journal of Computer and Systems Sciences 4, pages 205\u2013219, 1970.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"7_CR42","unstructured":"R. Milner. Communication and Concurrency. Prentice Hall, 1989."},{"key":"7_CR43","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/3-540-54233-7_141","volume-title":"Proceedings 18th ICALP","author":"K. Madlener","year":"1991","unstructured":"K. Madlener, P. Narendran, and F. Otto. A specialized completion procedure for monadic string-rewriting systems presenting groups. In Proceedings 18th ICALP, pages 279\u2013290. Springer, LNCS No 510, 1991."},{"key":"7_CR44","first-page":"119","volume":"113","author":"K. Madlener","year":"1993","unstructured":"K. Madlener, P. Narendran, F. Otto, and L. Zhang. On weakly confluent monadic string-rewriting systems. T.C.S. 113, pages 119\u2013165, 1993.","journal-title":"T.C.S."},{"key":"7_CR45","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings STACS\u20192000","author":"C. Morvan","year":"2000","unstructured":"C. Morvan. Rational graphs. In Proceedings STACS\u20192000. LNCS, 2000."},{"key":"7_CR46","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/BF02090778","volume":"23","author":"P. Narendran","year":"1990","unstructured":"P. Narendran. It is decidable whether a monadic Thue system is canonical over a regular set. Math. Systems Theory 23, pages 245\u2013254, 1990.","journal-title":"Math. Systems Theory"},{"key":"7_CR47","doi-asserted-by":"crossref","unstructured":"M. Nivat. On some families of languages related to the Dyck language. 2nd Annual Symposium on Theory of Computing, 1970.","DOI":"10.1145\/800161.805168"},{"key":"7_CR48","volume-title":"Symposia Mathematica","author":"M. Nivat","year":"1975","unstructured":"M. Nivat. On the interpretation of recursive polyadic program schemes. Symposia Mathematica, vol. 15, Academic press, New-York, 1975."},{"key":"7_CR49","first-page":"285","volume":"35","author":"F. Otto","year":"1987","unstructured":"F. Otto. On deciding the confluence of a finite string-rewriting system on a given congruence class. JCSS 35, pages 285\u2013310, 1987.","journal-title":"JCSS"},{"key":"7_CR50","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/BF01614148","volume":"2","author":"F. Otto","year":"1992","unstructured":"F. Otto. Completing a finite special string-rewriting system on the congruence class of the empty word. Applicable Algebra in Engineering Comm.Comput. 2, pages 257\u2013274, 1992.","journal-title":"Applicable Algebra in Engineering Comm.Comput."},{"key":"7_CR51","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF01213858","volume":"25","author":"F. Otto","year":"1992","unstructured":"F. Otto. The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems. Math. Systems Theory 25, pages 241\u2013251, 1992.","journal-title":"Math. Systems Theory"},{"key":"7_CR52","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/BF01178585","volume":"28","author":"F. Otto","year":"1991","unstructured":"F. Otto and L. Zhang. Decision problems for finite special string-rewriting systems that are confluent on some congruence class. Acta Informatica 28, pages 477\u2013510, 1991.","journal-title":"Acta Informatica"},{"key":"7_CR53","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BFb0017309","volume-title":"Concurrency and automata on infinite sequences","author":"D. Park","year":"1981","unstructured":"D. Park. Concurrency and automata on infinite sequences. LNCS 104, pages 167\u2013183, 1981."},{"key":"7_CR54","unstructured":"M.S. Paterson. Equivalence problems in a model of computation. Ph. D. Thesis, University of Cambridge, England, 1967."},{"key":"7_CR55","unstructured":"L. Pelecq. Isomorphismes et automorphismes des graphes context-free, \u00e9quationnels et automatiques. Th\u00e8se de doctorat, Universit\u00e9 Bordeaux I, Juin 1997."},{"key":"7_CR56","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1016\/S0022-0000(75)80057-2","volume":"11","author":"B.K. Rosen","year":"1975","unstructured":"B.K. Rosen. Program equivalence and context-free grammars. Journal of Computer and System Sciences 11, pages 358\u2013374, 1975.","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR57","doi-asserted-by":"crossref","unstructured":"J. Rutledge. On Ianov\u2019s program schemata. Journal of the Association for Computing Machinery, pages 1\u20139, 1964.","DOI":"10.1145\/321203.321204"},{"key":"7_CR58","first-page":"1","volume":"VII","author":"J. Sakarovitch","year":"1979","unstructured":"J. Sakarovitch. Syntaxe des langages de Chomsky, essai sur le d\u00e9terminisme. Th\u00e8se de doctorat d\u2019 \u00e9tat de l\u2019universit\u00e9 Paris VII, pages 1\u2013175, 1979.","journal-title":"Th\u00e8se de doctorat d\u2019 \u00e9tat de l\u2019universit\u00e9 Paris"},{"issue":"3","key":"7_CR59","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-0000(85)90055-8","volume":"31","author":"G. S\u00e9nizergues","year":"1985","unstructured":"G. S\u00e9nizergues. The equivalence and inclusion problems for NTS languages. J. Comput. System Sci. 31(3), pages 303\u2013331, 1985.","journal-title":"J. Comput. System Sci."},{"key":"7_CR60","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0304-3975(90)90048-M","volume":"71","author":"G. S\u00e9nizergues","year":"1990","unstructured":"G. S\u00e9nizergues. Some decision problems about controlled rewriting systems. TCS 71, pages 281\u2013346, 1990.","journal-title":"TCS"},{"key":"7_CR61","first-page":"16","volume":"28","author":"G. S\u00e9nizergues","year":"1992","unstructured":"G. S\u00e9nizergues. Definability in weak monadic second-order logic of some infinite graphs. In Dagstuhl seminar on Automata theory: Infinite computations. Wadern, Germany, volume 28, pages 16\u201316, 1992.","journal-title":"Dagstuhl seminar on Automata theory: Infinite computations. Wadern, Germany"},{"key":"7_CR62","series-title":"Lect Notes Comput Sci","first-page":"75","volume-title":"Term Rewriting, Advanced Course","author":"G. S\u00e9nizergues","year":"1994","unstructured":"G. S\u00e9nizergues. Formal languages and word-rewriting. In Term Rewriting, Advanced Course, pages 75\u201394. Springer, LNCS 909, edited by H. Comon and J.P. Jouannaud, 1994."},{"key":"7_CR63","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues. L(A) = L(B)? In Proceedings INFINITY 97, pages 1\u201326. Electronic Notes in Theoretical Computer Science 9, http:\/\/www.elsevier.nl\/locate\/entcs\/volume9.html , 1997.","DOI":"10.1016\/S1571-0661(05)80430-X"},{"key":"7_CR64","unstructured":"G. S\u00e9nizergues. L(A) = L(B)? Technical report, LaBRI, Universit\u00e9 Bordeaux I, report nr1161-97, 1997. Pages 1\u201371."},{"key":"7_CR65","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1007\/3-540-63165-8_221","volume-title":"Proceedings ICALP 97","author":"G. S\u00e9nizergues","year":"1997","unstructured":"G. S\u00e9nizergues. The Equivalence Problem for Deterministic Pushdown Automata is Decidable. In Proceedings ICALP 97, pages 671\u2013681. Springer, LNCS 1256, 1997."},{"key":"7_CR66","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues. Decidability of bisimulation equivalence for equational graphs of finite out-degree. In Rajeev Motwani, editor, Proceedings FOCS\u201998, pages 120\u2013129. IEEE Computer Society Press, 1998.","DOI":"10.1109\/SFCS.1998.743435"},{"key":"7_CR67","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0304-3975(97)00145-X","volume":"192","author":"G. S\u00e9nizergues","year":"1998","unstructured":"G. S\u00e9nizergues. A polynomial algorithm testing partial confluence of basic semi-Thue systems. Theoretical Computer Science 192, pages 55\u201375, 1998.","journal-title":"Theoretical Computer Science"},{"key":"7_CR68","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S0304-3975(99)00106-1","volume":"231","author":"G. S\u00e9nizergues","year":"2000","unstructured":"G. S\u00e9nizergues. Complete Formal Systems for Equivalence Problems. Theoretical Computer Science, 231:309\u2013334, 2000.","journal-title":"Theoretical Computer Science"},{"key":"7_CR69","unstructured":"G. S\u00e9nizergues. The bisimulation problem for equational graphs of finite out-degree. submitted to SIAM Journal on Computing; can be accessed at http:\/\/arXiv.org\/abs\/cs\/0008018 , pages 1\u201398, 2000."},{"key":"7_CR70","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00285-1","volume":"251","author":"G. S\u00e9nizergues","year":"2001","unstructured":"G. S\u00e9nizergues. L(A) = L(B)? decidability results from complete formal systems. Theoretical Computer Science, 251:1\u2013166, 2001.","journal-title":"Theoretical Computer Science"},{"key":"7_CR71","doi-asserted-by":"crossref","unstructured":"M. Solomon. Type definitions with parameters. In Conference Record of the Fifth Annual ACM Symposium on Principles of Programming Languages, pages 31\u201338, Tucson, Arizona, 1978. ACM SIGACT-SIGPLAN. Extended abstract.","DOI":"10.1145\/512760.512765"},{"key":"7_CR72","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/3-540-61604-7_57","volume-title":"Proceedings CONCUR 96","author":"C. Stirling","year":"1996","unstructured":"C. Stirling. Decidability of bisimulation equivalence for normed pushdown processes. In Proceedings CONCUR 96, pages 217\u2013232. Springer-Verlag, LNCS 1119, 1996."},{"key":"7_CR73","unstructured":"C. Stirling Decidability of dpda\u2019s equivalence. Technical report, Edinburgh ECS-LFCS-99-411, 1999. Pages 1\u201325, accepted for publication in TCS."},{"key":"7_CR74","unstructured":"L. Zhang. Weak confluence is tractable for finite string-rewriting systems. preprint, pages 1\u201310, 1991."},{"key":"7_CR75","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0020-0190(92)90082-7","volume":"44","author":"L. Zhang","year":"1992","unstructured":"L. Zhang. The pre-NTS property is undecidable for context-free grammars. IPL44, pages 181\u2013184, 1992.","journal-title":"IPL"}],"container-title":["Lecture Notes in Computer Science","Machines, Computations, and Universality"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45132-3_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T07:53:28Z","timestamp":1737532408000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45132-3_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540421214","9783540451327"],"references-count":75,"URL":"https:\/\/doi.org\/10.1007\/3-540-45132-3_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}