{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:29:30Z","timestamp":1742912970650,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540440406"},{"type":"electronic","value":"9783540456872"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45687-2_36","type":"book-chapter","created":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T08:57:47Z","timestamp":1192784267000},"page":"433-445","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["On the Complexity of Semantic Equivalences for Pushdown Automata and BPA"],"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,10,4]]},"reference":[{"key":"36_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/3-540-59293-8_206","volume-title":"Proceedings of CAAP\u201995","author":"P. Jan\u010dar","year":"1995","unstructured":"P. Jan\u010dar. High undecidability of weak bisimilarity for Petri nets. In Proceedings of CAAP\u201995, volume 915 of LNCS, pages 349\u2013363. Springer, 1995."},{"issue":"1\u20132","key":"36_CR2","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/S0304-3975(00)00027-X","volume":"258","author":"P. Jan\u010dar","year":"2001","unstructured":"P. Jan\u010dar, A. Ku\u010dera, and R. Mayr. Deciding bisimulation-like equivalences with finite-state processes. Theoretical Computer Science, 258(1\u20132):409\u2013433, 2001.","journal-title":"Theoretical Computer Science"},{"key":"36_CR3","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0304-3975(82)90125-6","volume":"27","author":"D. Kozen","year":"1983","unstructured":"D. Kozen. Results on the propositional \u03bc-calculus. Theoretical Computer Science, 27:333\u2013354, 1983.","journal-title":"Theoretical Computer Science"},{"key":"36_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/3-540-44464-5_11","volume-title":"Proceedings of ASIAN 2000","author":"A. Ku\u010dera","year":"2000","unstructured":"A. Ku\u010dera. On simulation-checking with sequential systems. In Proceedings of ASIAN 2000, volume 1961 of LNCS, pages 133\u2013148. Springer, 2000."},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"A. Ku\u010dera and R. Mayr. On the complexity of semantic equivalences for pushdown automata and BPA. Technical report FIMU-RS-2002-01, Faculty of Informatics, Masaryk University, 2002.","DOI":"10.1007\/3-540-45687-2_36"},{"issue":"2","key":"36_CR6","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1006\/inco.2001.3122","volume":"173","author":"A. Ku\u010dera","year":"2002","unstructured":"A. Ku\u010dera and R. Mayr. Simulation preorder over simple process algebras. Information and Computation, 173(2):184\u2013198, 2002.","journal-title":"Information and Computation"},{"issue":"1\u20132","key":"36_CR7","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1016\/S0304-3975(01)00094-9","volume":"270","author":"A. Ku\u010dera","year":"2002","unstructured":"A. Ku\u010dera and R. Mayr. Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time. Theoretical Computer Science, 270(1\u20132):677\u2013700, 2002.","journal-title":"Theoretical Computer Science"},{"key":"36_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1007\/3-540-44929-9_33","volume-title":"Proceedings of IFIP TCS\u20192000","author":"R. Mayr","year":"2000","unstructured":"R. Mayr. On the complexity of bisimulation problems for pushdown automata. In Proceedings of IFIP TCS\u20192000, volume 1872 of LNCS, pages 474\u2013488. Springer, 2000."},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues. Decidability of bisimulation equivalence for equational graphs of finite out-degree. In Proceedings of 39th Annual Symposium on Foundations of Computer Science, pages 120\u2013129. IEEE Computer Society Press, 1998.","DOI":"10.1109\/SFCS.1998.743435"},{"key":"36_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/3-540-45841-7_44","volume-title":"Proceedings of STACS 2002","author":"J. Srba","year":"2002","unstructured":"J. Srba. Strong bisimilarity and regularity of basic parallel processes is PSPACE-hard. In Proceedings of STACS 2002, volume 2285 of LNCS, pages 535\u2013546. Springer, 2002."},{"issue":"1","key":"36_CR11","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1006\/inco.1994.1028","volume":"110","author":"B. Steffen","year":"1994","unstructured":"B. Steffen and A. Ing\u00f3lfsd\u00f3ttir. Characteristic formulae for processes with divergence. Information and Computation, 110(1):149\u2013163, 1994.","journal-title":"Information and Computation"},{"key":"36_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1007\/BFb0055763","volume-title":"Proceedings of MFCS\u201998","author":"C. Stirling","year":"1998","unstructured":"C. Stirling. The joys of bisimulation. In Proceedings of MFCS\u201998, volume 1450 of LNCS, pages 142\u2013151. Springer, 1998."},{"key":"36_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00389-3","volume":"255","author":"C. Stirling","year":"2001","unstructured":"C. Stirling. Decidability of DPDA equivalence. Theoretical Computer Science, 255:1\u201331, 2001.","journal-title":"Theoretical Computer Science"},{"key":"36_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/3-540-56610-4_89","volume-title":"Proceedings of TAPSOFT\u201993","author":"W. Thomas","year":"1993","unstructured":"W. Thomas. On the ehrenfeucht-fra\u00efss\u00e9 game in theoretical computer science. In Proceedings of TAPSOFT\u201993, volume 668 of LNCS, pages 559\u2013568. Springer, 1993."},{"key":"36_CR15","unstructured":"R. van Glabbeek. The linear time\u2014branching time spectrum. Handbook of Process Algebra, pages 3\u201399, 1999."},{"key":"36_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/3-540-44450-5_10","volume-title":"Proceedings of FST&TCS 2000","author":"I. Walukiewicz","year":"2000","unstructured":"I. Walukiewicz. Model checking CTL properties of pushdown systems. In Proceedings of FST&TCS 2000, volume 1974 of LNCS, pages 127\u2013138. Springer, 2000."},{"issue":"2","key":"36_CR17","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.2000.2894","volume":"164","author":"I. Walukiewicz","year":"2001","unstructured":"I. Walukiewicz. Pushdown processes: Games and model-checking. Information and Computation, 164(2):234\u2013263, 2001.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2002"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45687-2_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T19:12:44Z","timestamp":1737486764000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-45687-2_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540440406","9783540456872"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-45687-2_36","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"4 October 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}