{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:11Z","timestamp":1725483731256},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540678236"},{"type":"electronic","value":"9783540449294"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44929-9_33","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T09:20:53Z","timestamp":1178356853000},"page":"474-488","source":"Crossref","is-referenced-by-count":9,"title":["On the Complexity of Bisimulation Problems for Pushdown Automata"],"prefix":"10.1007","author":[{"given":"Richard","family":"Mayr","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,24]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"J.C.M. Baeten and W.P. Weijland. Process algebra. Cambridge Tracts in Theoretical Computer Science, 18, 1990.","key":"33_CR1","DOI":"10.1017\/CBO9780511624193"},{"key":"33_CR2","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/BF03180566","volume":"4","author":"J. Balcazar","year":"1992","unstructured":"J. Balcazar, J. Gabarro, and M. Santha. Deciding bisimilarity is P-complete. Formal Aspects of Computing, 4:638\u2013648, 1992.","journal-title":"Formal Aspects of Computing"},{"key":"33_CR3","series-title":"Lect Notes Comput Sci","volume-title":"International Conference on Concurrency Theory (CONCUR\u201997)","author":"A. Bouajjani","year":"1997","unstructured":"A. Bouajjani, J. Esparza, and O. Maler. Reachability analysis of pushdown automata: application to model checking. In International Conference on Concurrency Theory (CONCUR\u201997), volume 1243 of LNCS. Springer Verlag, 1997."},{"key":"33_CR4","series-title":"Lect Notes Comput Sci","volume-title":"MFCS\u201995","author":"O. Burkart","year":"1995","unstructured":"O. Burkart, D. Caucal, and B. Steffen. An elementary bisimulation decision procedure for arbitrary context-free processes. In MFCS\u201995, volume 969 of LNCS. Springer Verlag, 1995."},{"key":"33_CR5","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of CONCUR\u201996","author":"O. Burkart","year":"1996","unstructured":"O. Burkart, D. Caucal, and B. Steffen. Bisimulation collapse and the process taxonomy. In U. Montanari and V. Sassone, editors, Proceedings of CONCUR\u201996, volume 1119 of LNCS. Springer Verlag, 1996."},{"key":"33_CR6","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0304-3975(92)90278-N","volume":"106","author":"D. Caucal","year":"1992","unstructured":"D. Caucal. On the regular structure of prefix rewriting. Journal of Theoretical Computer Science, 106:61\u201386, 1992.","journal-title":"Journal of Theoretical Computer Science"},{"key":"33_CR7","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of CONCUR 93","author":"S. Christensen","year":"1993","unstructured":"S. Christensen, Y. Hirshfeld, and F. Moller. Bisimulation equivalence is decidable for Basic Parallel Processes. In E. Best, editor, Proceedings of CONCUR 93, volume 715 of LNCS. Springer Verlag, 1993."},{"key":"33_CR8","series-title":"Lect Notes Comput Sci","volume-title":"Proc. of ICALP\u201999","author":"Y. Hirshfeld","year":"1999","unstructured":"Y. Hirshfeld and M. Jerrum. Bisimulation equivalence is decidable for normed process algebra. In Proc. of ICALP\u201999, volume 1644 of LNCS. Springer Verlag, 1999."},{"key":"33_CR9","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0304-3975(95)00064-X","volume":"158","author":"Y. Hirshfeld","year":"1996","unstructured":"Y. Hirshfeld, M. Jerrum, and F. Moller. A polynomial algorithm for deciding bisimilarity of normed context-free processes. Theoretical Computer Science, 158:143\u2013159, 1996.","journal-title":"Theoretical Computer Science"},{"key":"33_CR10","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1017\/S0960129500000992","volume":"6","author":"Y. Hirshfeld","year":"1996","unstructured":"Y. Hirshfeld, M. Jerrum, and F. Moller. A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes. Journal of Mathematical Structures in Computer Science, 6:251\u2013259, 1996.","journal-title":"Journal of Mathematical Structures in Computer Science"},{"unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison Wesley, 1979.","key":"33_CR11"},{"key":"33_CR12","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0304-3975(95)00037-W","volume":"148","author":"P. Jan\u010dar","year":"1995","unstructured":"P. Jan\u010dar. Undecidability of bisimilarity for Petri nets and some related problems. Theoretical Computer Science, 148:281\u2013301, 1995.","journal-title":"Theoretical Computer Science"},{"key":"33_CR13","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of ICALP\u201996","author":"P. Jan\u010dar","year":"1996","unstructured":"P. Jan\u010dar and J. Esparza. Deciding finiteness of Petri nets up to bisimulation. In F. Meyer auf der Heide and B. Monien, editors, Proceedings of ICALP\u201996, volume 1099 of LNCS. Springer Verlag, 1996."},{"key":"33_CR14","series-title":"Lect Notes Comput Sci","volume-title":"Proc. of ICALP\u201998","author":"P. Jan\u010dar","year":"1998","unstructured":"P. Jan\u010dar, A. Ku\u010dera, and R. Mayr. Deciding bisimulation-like equivalences with finite-state processes. In Proc. of ICALP\u201998, volume 1443 of LNCS. Springer Verlag, 1998."},{"key":"33_CR15","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of CONCUR\u201995","author":"P. Jan\u010dar","year":"1995","unstructured":"P. Jan\u010dar and F. Moller. Checking regular properties of Petri nets. In Insup Lee and Scott A. Smolka, editors, Proceedings of CONCUR\u201995, volume 962 of LNCS. Springer Verlag, 1995."},{"key":"33_CR16","series-title":"Lect Notes Comput Sci","volume-title":"Foundations of Software Technology and Theoretical Computer Science (FST&TCS\u201996)","author":"A. Ku\u010dera","year":"1996","unstructured":"A. Ku\u010dera. Regularity is decidable for normed PA processes in polynomial time. In Foundations of Software Technology and Theoretical Computer Science (FST&TCS\u201996), volume 1180 of LNCS, Springer Verlag, 1996."},{"key":"33_CR17","series-title":"Lect Notes Comput Sci","volume-title":"Proc. of CONCUR\u201999","author":"A. Ku\u010dera","year":"1999","unstructured":"A. Ku\u010dera and R. Mayr. Weak bisimilarity with infinite-state systems can be decided in polynomial time. In Proc. of CONCUR\u201999, volume 1664 of LNCS. Springer Verlag, 1999."},{"unstructured":"R. Lipton. The reachability problem requires exponential space. Technical Report 62, Department of Computer Science, Yale University, January 1976.","key":"33_CR18"},{"key":"33_CR19","series-title":"Lect Notes Comput Sci","volume-title":"Proc. of ICALP\u20192000","author":"R. Mayr","year":"2000","unstructured":"R. Mayr. On the complexity of bisimulation problems for Basic Parallel Processes. In Proc. of ICALP\u20192000, volume ? of LNCS.Springer Verlag, 2000."},{"issue":"1","key":"33_CR20","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1006\/inco.1999.2826","volume":"156","author":"R. Mayr","year":"2000","unstructured":"R. Mayr. Process rewrite systems. Information and Computation, 156(1):264\u2013286, 2000.","journal-title":"Information and Computation"},{"unstructured":"R. Milner. Communication and Concurrency. Prentice Hall, 1989.","key":"33_CR21"},{"key":"33_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-60915-6","volume-title":"Proceedings of CONCUR\u201996","author":"F. Moller","year":"1996","unstructured":"F. Moller. Infinite results. In Ugo Montanari and Vladimiro Sassone, editors, Proceedings of CONCUR\u201996, volume 1119 of LNCS. Springer Verlag, 1996."},{"key":"33_CR23","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/S0019-9958(80)90887-6","volume":"45","author":"M. Oyamaguchi","year":"1980","unstructured":"M. Oyamaguchi, N. Honda, and Y. Inagaki. The equivalence problem for real-time strict deterministic languages. Information and Control, 45:90\u2013115, 1980.","journal-title":"Information and Control"},{"issue":"6","key":"33_CR24","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"R. Paige and R. Tarjan. Three partition refinement algorithms. SIAM Journal of Computing, 16(6):973\u2013989, 1987.","journal-title":"SIAM Journal of Computing"},{"unstructured":"J.L. Peterson. Petri net theory and the modeling of systems. Prentice-Hall, 1981.","key":"33_CR25"},{"key":"33_CR26","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1007\/3-540-63165-8_221","volume-title":"Proceedings of ICALP\u201997","author":"G. S\u00e9nizergues","year":"1997","unstructured":"G. S\u00e9nizergues. The Equivalence Problem for Deterministic Pushdown Automata is Decidable. In Proceedings of ICALP\u201997, volume 1256 of LNCS, pages 671\u2013681. Springer Verlag, 1997."},{"unstructured":"G. S\u00e9nizergues. Decidability of bisimulation equivalence for equational graphs of finite out-degree. In Proc. of FOCS\u201998. IEEE, 1998.","key":"33_CR27"},{"doi-asserted-by":"crossref","unstructured":"J. St\u0159\u00edbrn\u00e1. Hardness results for weak bisimilarity of simple process algebras. Electronic Notes in Theoretical Computer Science (ENTCS), 18, 1998.","key":"33_CR28","DOI":"10.1016\/S1571-0661(05)80259-2"}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44929-9_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T14:41:06Z","timestamp":1556376066000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44929-9_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540678236","9783540449294"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-44929-9_33","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}