{"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":1761611215449,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540664253"},{"type":"electronic","value":"9783540483205"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48320-9_26","type":"book-chapter","created":{"date-parts":[[2007,11,15]],"date-time":"2007-11-15T13:52:42Z","timestamp":1195134762000},"page":"368-382","source":"Crossref","is-referenced-by-count":10,"title":["Weak Bisimilarity with Infinite-State Systems Can Be Decided in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Anton\u00edn","family":"Ku\u010dera","sequence":"first","affiliation":[]},{"given":"Richard","family":"Mayr","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,4,19]]},"reference":[{"key":"26_CR1","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/174130.174141","volume":"40","author":"J. C. M. Baeten","year":"1993","unstructured":"J. C. M. Baeten, J. A. Bergstra, and J. W. Klop. Decidability of bisimulation equivalence for processes generating context-free languages. JACM, 40:653\u2013682, 1993.","journal-title":"JACM"},{"doi-asserted-by":"crossref","unstructured":"J. C. M. Baeten and W. P. Weijland. Process Algebra. Number 18 in Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1990.","key":"26_CR2","DOI":"10.1017\/CBO9780511624193"},{"key":"26_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/3-540-63141-0_10","volume-title":"Proceedings of 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 Proceedings of CONCUR\u201997, volume 1243 of LNCS, pages 135\u2013150. Springer, 1997."},{"key":"26_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/3-540-60246-1_148","volume-title":"Proceedings of MFCS\u201995","author":"O. Burkart","year":"1995","unstructured":"O. Burkart, D. Caucal, and B. Steffen. An elementary decision procedure for arbitrary context-free processes. In Proceedings of MFCS\u201995, volume 969 of LNCS, pages 423\u2013433. Springer, 1995."},{"doi-asserted-by":"crossref","unstructured":"O. Burkart and J. Esparza. More infinite results. ENTCS, 5, 1997.","key":"26_CR5","DOI":"10.1016\/S1571-0661(05)80680-2"},{"issue":"4","key":"26_CR6","first-page":"339","volume":"24","author":"D. Caucal","year":"1990","unstructured":"D. Caucal. Graphes canoniques des graphes alg\u00e9briques. RAIRO, 24(4):339\u2013352, 1990.","journal-title":"RAIRO"},{"issue":"3","key":"26_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s002360050159","volume":"36","author":"I. \u010cern\u00e1","year":"1999","unstructured":"I. \u010cern\u00e1, M. K\u0159et\u00ednsk\u00fd, and A. Ku\u010dera. Comparing expressibility of normed BPAand normed BPP processes. Acta Informatica, 36(3):233\u2013256, 1999.","journal-title":"Acta Informatica"},{"key":"26_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/3-540-57208-2_11","volume-title":"Proceedings of CONCUR\u201993","author":"S. Christensen","year":"1993","unstructured":"S. Christensen, Y. Hirshfeld, and F. Moller. Bisimulation is decidable for all basic parallel processes. In Proceedings of CONCUR\u201993, volume 715 of LNCS, pages 143\u2013157. Springer, 1993."},{"key":"26_CR9","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:143\u2013148, 1995.","journal-title":"Information and Computation"},{"key":"26_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/3-540-60249-6_54","volume-title":"Proceedings of FCT\u201995","author":"J. Esparza","year":"1995","unstructured":"J. Esparza. Petri nets, commutative context-free grammars, and basic parallel processes. In Proceedings of FCT\u201995, volume 965 of LNCS, pages 221\u2013232. Springer, 1995."},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s002360050074","volume":"34","author":"J. Esparza","year":"1997","unstructured":"J. Esparza. Decidability of model checking for infinite-state concurrent systems. Acta Informatica, 34:85\u2013107, 1997.","journal-title":"Acta Informatica"},{"key":"26_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/3-540-49019-1_2","volume-title":"Proceedings of FoSSaCS\u201999","author":"J. Esparza","year":"1999","unstructured":"J. Esparza and J. Knop. An automata-theoretic approach to interprocedural data-flow analysis. In Proceedings of FoSSaCS\u201999, volume 1578 of LNCS, pages 14\u201330. Springer, 1999."},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0020-0190(92)90142-I","volume":"42","author":"J. F. Groote","year":"1992","unstructured":"J. F. Groote. A short proof of the decidability of bisimulation for normed BPA processes. Information Processing Letters, 42:167\u2013171, 1992.","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"Y. Hirshfeld. Bisimulation trees and the decidability of weak bisimulations. ENTCS, 5, 1996.","key":"26_CR14","DOI":"10.1016\/S1571-0661(05)80674-7"},{"key":"26_CR15","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. TCS, 158:143\u2013159, 1996.","journal-title":"TCS"},{"key":"26_CR16","first-page":"251","volume":"6","author":"Y. Hirshfeld","year":"1996","unstructured":"Y. Hirshfeld, M. Jerrum, and F. Moller. A polynomial algorithm for deciding bisimulation equivalence of normed basic parallel processes. MSCS, 6:251\u2013259, 1996.","journal-title":"MSCS"},{"unstructured":"J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.","key":"26_CR17"},{"doi-asserted-by":"crossref","unstructured":"H. H\u00fcttel and C. Stirling. Actions speak louder than words: Proving bisimilarity for contextfree processes. In Proceedings of LICS\u201991, pages 376\u2013386. IEEE Computer Society Press, 1991.","key":"26_CR18","DOI":"10.1109\/LICS.1991.151661"},{"key":"26_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/BFb0055053","volume-title":"Proceedings 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 Proceedings of ICALP\u201998, volume 1443 of LNCS, pages 200\u2013211. Springer, 1998."},{"unstructured":"A. Ku\u010dera. On effective decomposability of sequential behaviours. TCS. To appear.","key":"26_CR20"},{"doi-asserted-by":"crossref","unstructured":"A. Ku\u010dera and R. Mayr. Weak bisimilarity with infinite-state systems can be decided in polynomial time. Technical Report TUM-I9830, Institut f\u00fcr Informatik, TU-M\u00fcnchen, 1998.","key":"26_CR21","DOI":"10.1007\/3-540-48320-9_26"},{"key":"26_CR22","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of ICALP\u201999","author":"A. Ku\u010dera","year":"1999","unstructured":"A. Ku\u010dera and R. Mayr. Simulation preorder on simple process algebras. In Proceedings of ICALP\u201999, LNCS. Springer, 1999. To apper."},{"unstructured":"R. Mayr. Process rewrite systems. Information and Computation. To appear.","key":"26_CR23"},{"key":"26_CR24","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/3-540-62034-6_40","volume-title":"Proceedings of FST&TCS\u201996","author":"R. Mayr","year":"1996","unstructured":"R. Mayr. Weak bisimulation andmodel checking for basic parallel processes. In Proceedings of FST&TCS\u201996, volume 1180 of LNCS, pages 88\u201399. Springer, 1996."},{"doi-asserted-by":"crossref","unstructured":"R. Mayr. Strict lower bounds for model checking BPA. ENTCS, 18, 1998.","key":"26_CR25","DOI":"10.1016\/S1571-0661(05)80256-7"},{"unstructured":"R. Milner. Communication and Concurrency. Prentice-Hall, 1989.","key":"26_CR26"},{"key":"26_CR27","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/3-540-61604-7_56","volume-title":"Proceedings of CONCUR\u201996","author":"F. Moller","year":"1996","unstructured":"F. Moller. Infinite results. In Proceedings of CONCUR\u201996, volume 1119 of LNCS, pages 195\u2013216. Springer, 1996."},{"issue":"6","key":"26_CR28","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":"26_CR29","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BFb0017309","volume-title":"Proceedings 5thGI Conference","author":"D. M. R. Park","year":"1981","unstructured":"D. M. R. Park. Concurrency and automata on infinite sequences. In Proceedings 5th GI Conference, volume 104 of LNCS, pages 167\u2013183. Springer, 1981."},{"doi-asserted-by":"crossref","unstructured":"J. St\u0159\u00edbrn\u00e1. Hardness results for weak bisimilarity of simple process algebras. ENTCS, 18, 1998.","key":"26_CR30","DOI":"10.1016\/S1571-0661(05)80259-2"}],"container-title":["Lecture Notes in Computer Science","CONCUR\u201999 Concurrency Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48320-9_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T10:58:10Z","timestamp":1737543490000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48320-9_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540664253","9783540483205"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-48320-9_26","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}