{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,14]],"date-time":"2025-02-14T05:24:59Z","timestamp":1739510699853,"version":"3.37.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642106712"},{"type":"electronic","value":"9783642106729"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10672-9_23","type":"book-chapter","created":{"date-parts":[[2009,12,2]],"date-time":"2009-12-02T09:08:11Z","timestamp":1259744891000},"page":"327-342","source":"Crossref","is-referenced-by-count":0,"title":["Branching Bisimilarity between Finite-State Systems and BPA or Normed BPP Is Polynomial-Time Decidable"],"prefix":"10.1007","author":[{"given":"Hongfei","family":"Fu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/B978-044482830-9\/50027-8","volume-title":"Handbook of Process Algebra","author":"O. Burkart","year":"2001","unstructured":"Burkart, O., Caucal, D., Moller, F., Steffen, B.: Verification on infinite structures. In: Bergsta, J., Ponse, A., Smolka, S. (eds.) Handbook of Process Algebra, pp. 545\u2013623. Elsevier Science, Amsterdam (2001)"},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1006\/inco.1999.2826","volume":"156","author":"R. Mayr","year":"2000","unstructured":"Mayr, R.: Process rewrite systems. Inf. Comput.\u00a0156, 264\u2013286 (2000)","journal-title":"Inf. Comput."},{"key":"23_CR3","first-page":"163","volume":"78","author":"J. Srba","year":"2002","unstructured":"Srba, J.: Roadmap of infinite results. Bulletin of the EATCS\u00a078, 163\u2013175 (2002)","journal-title":"Bulletin of the EATCS"},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/174130.174141","volume":"40","author":"J.C.M. Baeten","year":"1993","unstructured":"Baeten, J.C.M., Bergstra, J.A., Klop, J.W.: Decidability of bisimulation equivalence for processes generating context-free languages. J. ACM\u00a040, 653\u2013682 (1993)","journal-title":"J. ACM"},{"key":"23_CR5","volume-title":"Introduction to Automata Theory, Languages, and Computations","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computations. Addison-Wesley, Reading (1979)"},{"key":"23_CR6","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1006\/inco.1995.1129","volume":"121","author":"S. Christensen","year":"1995","unstructured":"Christensen, S., H\u00fcttel, H., Stirling, C.: Bisimulation equivalence is decidable for all context-free processes. Inf. Comput.\u00a0121, 143\u2013148 (1995)","journal-title":"Inf. Comput."},{"key":"23_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/3-540-57208-2_11","volume-title":"CONCUR\u201993","author":"S. Christensen","year":"1993","unstructured":"Christensen, S., Hirshfeld, Y., Moller, F.: Bisimulation equivalence is decidable for basic parallel processes. In: Best, E. (ed.) CONCUR 1993. LNCS, vol.\u00a0715, pp. 143\u2013157. Springer, Heidelberg (1993)"},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1007\/3-540-45465-9_61","volume-title":"Automata, Languages and Programming","author":"J. Srba","year":"2002","unstructured":"Srba, J.: Strong bisimilarity and regularity of basic process algebra is PSPACE-hard. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 716\u2013727. Springer, Heidelberg (2002)"},{"key":"23_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/3-540-45841-7_44","volume-title":"STACS 2002","author":"J. Srba","year":"2002","unstructured":"Srba, J.: Strong bisimilarity and regularity of basic parallel processes is PSPACE-hard. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 535\u2013546. Springer, Heidelberg (2002)"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"Jan\u010dar, P.: Strong bisimilarity on basic parallel processes is pspace-complete. In: LICS, p. 218 (2003)","DOI":"10.1109\/LICS.2003.1210061"},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0304-3975(95)00064-X","volume":"158","author":"Y. Hirshfeld","year":"1996","unstructured":"Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial algorithm for deciding bisimilarity of normed context-free processes. Theor. Comput. Sci.\u00a0158, 143\u2013159 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR12","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1017\/S0960129500000992","volume":"6","author":"Y. Hirshfeld","year":"1996","unstructured":"Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial-time algorithm for deciding bisimulation equivalence of normed basic parallel processes. Mathematical Structures in Computer Science\u00a06, 251\u2013259 (1996)","journal-title":"Mathematical Structures in Computer Science"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1016\/S0304-3975(00)00027-X","volume":"258","author":"P. Jan\u010dar","year":"2001","unstructured":"Jan\u010dar, P., Ku\u010dera, A., Mayr, R.: Deciding bisimulation-like equivalences with finite-state processes. Theor. Comput. Sci.\u00a0258, 409\u2013433 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0304-3975(00)00101-8","volume":"256","author":"R. Mayr","year":"2001","unstructured":"Mayr, R.: Decidability of model checking with the temporal logic ef. Theor. Comput. Sci.\u00a0256, 31\u201362 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/11590156_17","volume-title":"FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science","author":"M. Kret\u00ednsk\u00fd","year":"2005","unstructured":"Kret\u00ednsk\u00fd, M., Reh\u00e1k, V., Strejcek, J.: Reachability of hennessy-milner properties for weakly extended PRS. In: Sarukkai, S., Sen, S. (eds.) FSTTCS 2005. LNCS, vol.\u00a03821, pp. 213\u2013224. Springer, Heidelberg (2005)"},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1016\/S0304-3975(01)00094-9","volume":"270","author":"A. Kucera","year":"2002","unstructured":"Kucera, A., Mayr, R.: Weak bisimilarity between finite-state systems and bpa or normed bpp is decidable in polynomial time. Theor. Comput. Sci.\u00a0270, 677\u2013700 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR17","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/233551.233556","volume":"43","author":"R.J. Glabbeek van","year":"1996","unstructured":"van Glabbeek, R.J., Weijland, W.P.: Branching time and abstraction in bisimulation semantics. J. ACM\u00a043, 555\u2013600 (1996)","journal-title":"J. ACM"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Baeten, J., Weijland, W.: Process Algebra. Cambridge (1990)","DOI":"10.1017\/CBO9780511624193"},{"key":"23_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/3-540-55179-4_2","volume-title":"Computer Aided Verification","author":"H. H\u00fcttel","year":"1992","unstructured":"H\u00fcttel, H.: Silence is golden: Branching bisimilarity is decidable for context-free processes. In: Larsen, K.G., Skou, A. (eds.) CAV 1991. LNCS, vol.\u00a0575, pp. 2\u201312. Springer, Heidelberg (1992)"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Kucera, A., Mayr, R.: A generic framework for checking semantic equivalences between pushdown automata and finite-state automata. In: IFIP TCS, pp. 395\u2013408 (2004)","DOI":"10.1007\/1-4020-8141-3_31"},{"key":"23_CR21","first-page":"339","volume":"24","author":"D. Caucal","year":"1990","unstructured":"Caucal, D.: Graphes canoniques de graphes alg\u00e9briques. ITA\u00a024, 339\u2013352 (1990)","journal-title":"ITA"},{"key":"23_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1007\/BFb0032063","volume-title":"Automata, Languages and Programming","author":"J.F. Groote","year":"1990","unstructured":"Groote, J.F., Vaandrager, F.W.: An efficient algorithm for branching bisimulation and stuttering equivalence. In: Paterson, M. (ed.) ICALP 1990. LNCS, vol.\u00a0443, pp. 626\u2013638. Springer, Heidelberg (1990)"},{"key":"23_CR23","unstructured":"Fu, H.: Branching bisimilarity between finite-state systems and bpa or normed bpp is polynomial-time decidable, http:\/\/basics.sjtu.edu.cn\/~hongfei\/"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10672-9_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T15:33:14Z","timestamp":1739460794000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10672-9_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642106712","9783642106729"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10672-9_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}