{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:55Z","timestamp":1761611215610},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540677154"},{"type":"electronic","value":"9783540450221"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45022-x_29","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T23:57:25Z","timestamp":1194998245000},"page":"329-341","source":"Crossref","is-referenced-by-count":9,"title":["On the Complexity of Bisimulation Problems for Basic Parallel Processes"],"prefix":"10.1007","author":[{"given":"Richard","family":"Mayr","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,2,18]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"J.C.M. Baeten and W.P. Weijland. Process algebra. Cambridge Tracts in Theoretical Computer Science, 18, 1990.","DOI":"10.1017\/CBO9780511624193"},{"key":"29_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":"29_CR3","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":"29_CR4","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":"29_CR5","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":"29_CR6","unstructured":"S. Christensen. Decidability and Decomposition in Process Algebras. PhD thesis, Edinburgh University, 1993."},{"key":"29_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":"29_CR8","series-title":"Lect Notes Comput Sci","volume-title":"Fundamentals of Computation Theory","author":"J. Esparza","year":"1995","unstructured":"J. Esparza. Petri nets, commutative context-free grammars and Basic Parallel Processes. In Horst Reichel, editor, Fundamentals of Computation Theory, volume 965 of LNCS. Springer Verlag, 1995."},{"key":"29_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/3-540-60045-0_62","volume-title":"CAV\u201995","author":"J. Esparza","year":"1995","unstructured":"J. Esparza and A. Kiehn. On the model checking problem for branching time logics and Basic Parallel Processes. In CAV\u201995, volume 939 of LNCS, pages 353\u2013366. Springer Verlag, 1995."},{"key":"29_CR10","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":"29_CR11","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":"29_CR12","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"},{"key":"29_CR13","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":"29_CR14","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":"29_CR15","series-title":"Lect Notes Comput Sci","volume-title":"In Proc. of ICALP\u201998","author":"P. Jan\u010dar","year":"1998","unstructured":"P. Jan\u010dar, A. Kucera, and R. Mayr. Deciding bisimulation-like equivalences with finite-state processes. In Proc. of ICALP\u201998, volume 1443 of LNCS. Springer Verlag, 1998."},{"key":"29_CR16","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":"29_CR17","series-title":"Lect Notes Comput Sci","volume-title":"Foundations of Software Technology and Theoretical Computer Science (FST&TCS\u201996)","author":"A. Kucera","year":"1996","unstructured":"A. Kucera. 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":"29_CR18","series-title":"Lect Notes Comput Sci","volume-title":"In Proc. of CONCUR\u201999","author":"A. Kucera","year":"1999","unstructured":"A. Kucera 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."},{"key":"29_CR19","unstructured":"R. Lipton. The reachability problem requires exponential space. Technical Report 62, Department of Computer Science, Yale University, January 1976."},{"key":"29_CR20","series-title":"Lect Notes Comput Sci","volume-title":"Foundations of Software Technology and Theoretical Computer Science (FST&TCS\u201996)","author":"R. Mayr","year":"1996","unstructured":"R. Mayr. Weak bisimulation and model checking for Basic Parallel Processes. In Foundations of Software Technology and Theoretical Computer Science (FST&TCS\u201996), volume 1180 of LNCS. Springer Verlag, 1996."},{"key":"29_CR21","doi-asserted-by":"crossref","unstructured":"R. Mayr. Tableau methods for PA-processes. In D. Galmiche, editor, Analytic Tableaux and Related Methods (TABLEAUX\u201997), volume 1227 of LNAI. Springer Verlag, 1997.","DOI":"10.1007\/BFb0027420"},{"key":"29_CR22","unstructured":"R. Mayr. Decidability and Complexity of Model Checking Problems for Infinite-State Systems. PhD thesis, TU-M\u00fcnchen, 1998."},{"key":"29_CR23","doi-asserted-by":"crossref","unstructured":"R. Mayr. On the complexity of bisimulation problems for pushdown automata. 2000.","DOI":"10.1007\/3-540-44929-9_33"},{"issue":"1","key":"29_CR24","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"},{"key":"29_CR25","unstructured":"R. Milner. Communication and Concurrency. Prentice Hall, 1989."},{"key":"29_CR26","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."},{"issue":"6","key":"29_CR27","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"},{"key":"29_CR28","unstructured":"J.L. Peterson. Petri net theory and the modeling of systems. Prentice-Hall, 1981."},{"key":"29_CR29","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues. Decidability of bisimulation equivalence for equational graphs of finite out-degree. In Proc. of FOCS\u201998. IEEE, 1998.","DOI":"10.1109\/SFCS.1998.743435"},{"key":"29_CR30","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1007\/BFb0055763","volume-title":"Proc. of MFCS\u201998","author":"C. Stirling","year":"1998","unstructured":"C. Stirling. The joys of bisimulation. In Proc. of MFCS\u201998, volume 1450 of LNCS, pages 142\u2013151. Springer Verlag, 1998."},{"key":"29_CR31","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.","DOI":"10.1016\/S1571-0661(05)80259-2"},{"key":"29_CR32","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/3-540-56610-4_89","volume-title":"Proc. of TAPSOFT\u201993","author":"W. Thomas","year":"1993","unstructured":"W. Thomas. On the Ehrenfeucht-Fra\u00efss\u00e9 game in theoretical computer science. In Proc. of TAPSOFT\u201993, volume 668 of LNCS, pages 559\u2013568. Springer Verlag, 1993."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45022-X_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T11:25:25Z","timestamp":1556969125000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45022-X_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540677154","9783540450221"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-45022-x_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}