{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T18:10:15Z","timestamp":1726251015228},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,12,3]],"date-time":"2021-12-03T00:00:00Z","timestamp":1638489600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,12,3]],"date-time":"2021-12-03T00:00:00Z","timestamp":1638489600000},"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":["Front. Comput. Sci."],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s11704-021-0340-x","type":"journal-article","created":{"date-parts":[[2021,12,3]],"date-time":"2021-12-03T02:02:27Z","timestamp":1638496947000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The parametric complexity of bisimulation equivalence of normed pushdown automata"],"prefix":"10.1007","volume":"16","author":[{"given":"Wenbo","family":"Zhang","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,12,3]]},"reference":[{"key":"340_CR1","doi-asserted-by":"crossref","unstructured":"Park D. Concurrency and automata on infinite sequences. In: Proceedings of the 5th GI Conference, Lecture Notes in Computer Science. 1981, 167\u2013183","DOI":"10.1007\/BFb0017309"},{"key":"340_CR2","volume-title":"Communication and concurrency","author":"R Milner","year":"1989","unstructured":"Milner R. Communication and concurrency. 1st ed. New Jersey: Prentice-Hall, Inc., 1989","edition":"1st ed."},{"issue":"3","key":"340_CR3","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/233551.233556","volume":"43","author":"R J Van Glabbeek","year":"1996","unstructured":"Van Glabbeek R J, Weijland W P. Branching time and abstraction in bisimulation semantics. Journal of the ACM (JACM), 1996, 43(3): 555\u2013600","journal-title":"Journal of the ACM (JACM)"},{"key":"340_CR4","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J Hopcroft","year":"1979","unstructured":"Hopcroft J, Ullman J. Introduction to Automata Theory, Languages and Computation. 1st ed. New York: Addison-Wesley Publishing Company, 1979","edition":"1st ed."},{"issue":"6","key":"340_CR5","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1016\/S0019-9958(66)80019-0","volume":"9","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg S, Greibach S. Deterministic context free languages. Information and Control, 1966, 9(6): 620\u2013648","journal-title":"Information and Control"},{"issue":"1\u20132","key":"340_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00285-1","volume":"251","author":"G S\u00e9nizergues","year":"2001","unstructured":"S\u00e9nizergues G. L(A)=L(B)? Decidability results from complete formal systems Theoretical Computer Science, 2001, 251(1\u20132): 1\u2013166","journal-title":"Theoretical Computer Science"},{"key":"340_CR7","doi-asserted-by":"crossref","unstructured":"Stirling C. Deciding DPDA equivalence is primitive recursive. In: Proceedings of the 29th International Colloquium on Automata, Languages, and Programming. 2002, 821\u2013832","DOI":"10.1007\/3-540-45465-9_70"},{"key":"340_CR8","doi-asserted-by":"crossref","unstructured":"Jan\u010dar P. Equivalences of pushdown systems are hard. In: Proceedings of the 17th International Conference on Foundations of Software Science and Computation Structures. 2014, 1\u201328","DOI":"10.1007\/978-3-642-54830-7_1"},{"key":"340_CR9","doi-asserted-by":"crossref","unstructured":"S\u00e9nizergues G. Decidability of bisimulation equivalence for equational graphs of finite out-degree. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science. 1998, 120\u2013129","DOI":"10.1109\/SFCS.1998.743435"},{"issue":"5","key":"340_CR10","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539700377256","volume":"34","author":"G S\u00e9nizergues","year":"2005","unstructured":"S\u00e9nizergues G. The bisimulation problem for equational graphs of finite out-degree. SIAM Journal on Computing, 2005, 34(5): 1025\u20131106","journal-title":"SIAM Journal on Computing"},{"key":"340_CR11","doi-asserted-by":"crossref","unstructured":"Srba J. Undecidability of weak bisimilarity for pushdown processes. In: Proceedings of International Conference on Concurrency Theory. 2002, 579\u2013594","DOI":"10.1007\/3-540-45694-5_38"},{"key":"340_CR12","doi-asserted-by":"crossref","unstructured":"Yin Q, Fu Y, He C, Huang M, Tao X. Branching bisimilarity checking for PRS. In: Proceedings of International Colloquium on Automata, Languages, and Programming. 2014, 363\u2013374","DOI":"10.1007\/978-3-662-43951-7_31"},{"key":"340_CR13","doi-asserted-by":"crossref","unstructured":"Jan\u010dar P, Schmitz S. Bisimulation equivalence of first-order grammars is Ackermann-complete. In: Proceedings of the 34th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). 2019, 1\u201312","DOI":"10.1109\/LICS.2019.8785848"},{"key":"340_CR14","doi-asserted-by":"crossref","unstructured":"Jan\u010dar P. Decidability of DPDA language equivalence via first-order grammars. In: Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science. 2012, 415\u2013424","DOI":"10.1109\/LICS.2012.51"},{"issue":"7","key":"340_CR15","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1016\/j.ic.2010.01.003","volume":"208","author":"A Ku\u010dera","year":"2010","unstructured":"Ku\u010dera A, Mayr R. On the complexity of checking semantic equivalences between pushdown processes and finite-state processes. Information and Computation, 2010, 208(7): 772\u2013796","journal-title":"Information and Computation"},{"key":"340_CR16","doi-asserted-by":"crossref","unstructured":"Benedikt M, G\u00f6ller S, Kiefer S, Murawski A S. Bisimilarity of pushdown automata is nonelementary. In: Proceedings of the 28th Annual ACM\/IEEE Symposium on Logic in Computer Science. 2013, 488\u2013498","DOI":"10.1109\/LICS.2013.55"},{"key":"340_CR17","unstructured":"Zhang W, Yin Q, Long H, Xu X. Bisimulation equivalence of pushdown automata is Ackermann-complete. In: Proceedings of 47th International Colloquium on Automata, Languages, and Programming. 2020, 141: 1\u201314"},{"issue":"4","key":"340_CR18","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.ipl.2012.12.004","volume":"113","author":"S Kiefer","year":"2013","unstructured":"Kiefer S. BPA bisimilarity is EXPTIME-hard. Information Processing Letters, 2013, 113(4): 101\u2013106","journal-title":"Information Processing Letters"},{"key":"340_CR19","doi-asserted-by":"crossref","unstructured":"Burkart O, Caucal D, Steffen B. An elementary bisimulation decision procedure for arbitrary context-free processes. In: Proceedings of the 20th International Symposium on Mathematical Foundations of Computer Science. 1995, 423\u2013433","DOI":"10.1007\/3-540-60246-1_148"},{"key":"340_CR20","doi-asserted-by":"crossref","unstructured":"Jan\u010dar P. Bisimilarity on basic process algebra is in 2-Exptime (an explicit proof). preprint arXiv: 1207.2479, 2012","DOI":"10.2168\/LMCS-9(1:10)2013"},{"issue":"4","key":"340_CR21","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1016\/j.jcss.2013.11.003","volume":"80","author":"S B\u00f6hm","year":"2014","unstructured":"B\u00f6hm S, G\u00f6ller S, Jan\u010dar P. Bisimulation equivalence and regularity for real-time one-counter automata. Journal of Computer and System Sciences, 2014, 80(4): 720\u2013743","journal-title":"Journal of Computer and System Sciences"},{"issue":"1\u20132","key":"340_CR22","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. Theoretical Computer Science, 1996, 158(1\u20132): 143\u2013159","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"340_CR23","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/BF03180566","volume":"4","author":"J Balc\u00e1zar","year":"1992","unstructured":"Balc\u00e1zar J, Gabarro J, Santha M. Deciding bisimilarity is P-complete. Formal aspects of computing, 1992, 4(1): 638\u2013648","journal-title":"Formal aspects of computing"},{"issue":"1","key":"340_CR24","first-page":"3","volume":"8","author":"S Schmitz","year":"2016","unstructured":"Schmitz S. Complexity hierarchies beyond elementary. ACM Transactions on Computation Theory (TOCT), 2016, 8(1): 3","journal-title":"ACM Transactions on Computation Theory (TOCT)"},{"key":"340_CR25","doi-asserted-by":"crossref","unstructured":"Thomas W. On the ehrenfeucht-fra\u00efss\u00e9 game in theoretical computer science. In: Proceedings of Colloquium on Trees in Algebra and Programming. 1993, 559\u2013568","DOI":"10.1007\/3-540-56610-4_89"},{"issue":"1","key":"340_CR26","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/1326554.1326559","volume":"55","author":"P Jan\u010dar","year":"2008","unstructured":"Jan\u010dar P, Srba J. Undecidability of bisimilarity by Defender\u2019s forcing. Journal of the ACM (JACM), 2008, 55(1): 5","journal-title":"Journal of the ACM (JACM)"},{"key":"340_CR27","unstructured":"Srba J. Applications of the existential quantification technique. In: Proceedings of the 4th International Workshop on Verification of Infinite-State Systems (INFINITY02). 2002, 151\u2013152"},{"issue":"6\u20137","key":"340_CR28","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/s00236-003-0116-9","volume":"39","author":"J Srba","year":"2003","unstructured":"Srba J. Strong bisimilarity of simple process algebras: Complexity lower bounds. Acta Informatica, 2003, 39(6\u20137): 469\u2013499","journal-title":"Acta Informatica"},{"issue":"2","key":"340_CR29","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0304-3975(97)00216-8","volume":"195","author":"C Stirling","year":"1998","unstructured":"Stirling C. Decidability of bisimulation equivalence for normed pushdown processes. Theoretical Computer Science, 1998, 195(2): 113\u2013131","journal-title":"Theoretical Computer Science"},{"key":"340_CR30","doi-asserted-by":"crossref","unstructured":"Stirling C. Decidability of bisimulation equivalence for normed pushdown processes. In: Proceedings of the 7th International Conference on Concurrency Theory. 1996, 217\u2013232","DOI":"10.1007\/3-540-61604-7_57"},{"key":"340_CR31","unstructured":"Jan\u010dar P. Equivalence of pushdown automata via first-order grammars. arXiv: 1812.03518, 2018"},{"key":"340_CR32","doi-asserted-by":"crossref","unstructured":"Schmitz S. Complexity bounds for ordinal-based termination. In: Proceedings of the 8th International Workshop on Reachability Problems. 2014, 1\u201319","DOI":"10.1007\/978-3-319-11439-2_1"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-021-0340-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11704-021-0340-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-021-0340-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T17:19:44Z","timestamp":1726247984000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11704-021-0340-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,3]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["340"],"URL":"https:\/\/doi.org\/10.1007\/s11704-021-0340-x","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"type":"print","value":"2095-2228"},{"type":"electronic","value":"2095-2236"}],"subject":[],"published":{"date-parts":[[2021,12,3]]},"assertion":[{"value":"13 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"164405"}}