{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:31Z","timestamp":1750220791564,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T00:00:00Z","timestamp":1594166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100005304","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["LIFOUNDATIONS"],"award-info":[{"award-number":["LIFOUNDATIONS"]}],"id":[{"id":"10.13039\/501100005304","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Center of Science Poland","award":["2016\/22\/E\/ST6\/00041"],"award-info":[{"award-number":["2016\/22\/E\/ST6\/00041"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,8]]},"DOI":"10.1145\/3373718.3394827","type":"proceedings-article","created":{"date-parts":[[2020,5,26]],"date-time":"2020-05-26T00:23:18Z","timestamp":1590452598000},"page":"521-534","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Bisimulation Finiteness of Pushdown Systems Is Elementary"],"prefix":"10.1145","author":[{"given":"Stefan","family":"G\u00f6ller","sequence":"first","affiliation":[{"name":"University of Kassel, School of Electrical Engineering and Computer Science, Kassel, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Parys","sequence":"additional","affiliation":[{"name":"University of Warsaw, Institute of Informatics, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,8]]},"reference":[{"volume-title":"STACS","year":"2006","author":"B\u00e1r\u00e1ny Vince","key":"e_1_3_2_1_1_1"},{"volume-title":"Bisimilarity of Pushdown Automata Is Nonelementary. In 28th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2013","year":"2013","author":"Benedikt Michael","key":"e_1_3_2_1_2_1"},{"key":"e_1_3_2_1_3_1","unstructured":"Johan van Benthem. 1976. Modal Correspondence Theory. Ph.D. Dissertation. University of Amsterdam. http:\/\/www.illc.uva.nl\/Research\/Publications\/Dissertations\/HDS-06-Johan-van-Benthem.text.pdf Johan van Benthem. 1976. Modal Correspondence Theory. Ph.D. Dissertation. University of Amsterdam. http:\/\/www.illc.uva.nl\/Research\/Publications\/Dissertations\/HDS-06-Johan-van-Benthem.text.pdf"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.11.003"},{"key":"e_1_3_2_1_5_1","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17","volume":"18","author":"Christopher","year":"2012"},{"key":"e_1_3_2_1_6_1","unstructured":"Facundo Carreiro. 2015. PDL Is the Bisimulation-Invariant Fragment of Weak Chain Logic See [34] 341--352. https:\/\/doi.org\/10.1109\/LICS. 2015.40 Facundo Carreiro. 2015. PDL Is the Bisimulation-Invariant Fragment of Weak Chain Logic See [34] 341--352. https:\/\/doi.org\/10.1109\/LICS. 2015.40"},{"volume-title":"Graph Rewriting: An Algebraic and Logic Approach. See [33], 193--242. https:\/\/doi.org\/10.1016\/b978-0-444-88074-1.50010-x","year":"1990","author":"Courcelle Bruno","key":"e_1_3_2_1_7_1"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Sebastian Enqvist Fatemeh Seifan and Yde Venema. 2015. Monadic Second-Order Logic and Bisimulation Invariance for Coalgebras See [34] 353--365. https:\/\/doi.org\/10.1109\/LICS.2015.41 Sebastian Enqvist Fatemeh Seifan and Yde Venema. 2015. Monadic Second-Order Logic and Bisimulation Invariance for Coalgebras See [34] 353--365. https:\/\/doi.org\/10.1109\/LICS.2015.41","DOI":"10.1109\/LICS.2015.41"},{"volume-title":"Tools and Algorithms for the Construction and Analysis of Systems, 12th International Conference, TACAS 2006 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS","year":"2006","author":"Esparza Javier","key":"e_1_3_2_1_9_1"},{"volume-title":"CONCUR '90, Theories of Concurrency: Unification and Extension","year":"1990","author":"van Glabbeek Rob J.","key":"e_1_3_2_1_10_1"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/322307.322317"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61604-7_60"},{"key":"e_1_3_2_1_13_1","unstructured":"Petr Jan\u010dar. 2013. Bisimulation Equivalence of First-Order Grammars Is Ackermann-Hard. CoRR abs\/1312.3910 (2013). arXiv:1312.3910 Petr Jan\u010dar. 2013. Bisimulation Equivalence of First-Order Grammars Is Ackermann-Hard. CoRR abs\/1312.3910 (2013). arXiv:1312.3910"},{"key":"e_1_3_2_1_14_1","unstructured":"Petr Jan\u010dar. 2013. Finiteness up to Bisimilarity Is Decidable for Pushdown Processes. CoRR abs\/1305.0516v1 (2013). arXiv:1305.0516v1 Petr Jan\u010dar. 2013. Finiteness up to Bisimilarity Is Decidable for Pushdown Processes. CoRR abs\/1305.0516v1 (2013). arXiv:1305.0516v1"},{"key":"e_1_3_2_1_15_1","volume-title":"Bisimulation Equivalence. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016","volume":"58","author":"Jan\u010dar Petr","year":"2016"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Petr Jan\u010dar. 2019. Deciding Semantic Finiteness of Pushdown Processes and First-Order Grammars w.r.t. Bisimulation Equivalence. J. Comput. System Sci. (2019). https:\/\/doi.org\/10.1016\/j.jcss.2019.10.002 Petr Jan\u010dar. 2019. Deciding Semantic Finiteness of Pushdown Processes and First-Order Grammars w.r.t. Bisimulation Equivalence. J. Comput. System Sci. (2019). https:\/\/doi.org\/10.1016\/j.jcss.2019.10.002","DOI":"10.1016\/j.jcss.2019.10.002"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785848"},{"key":"e_1_3_2_1_18_1","volume-title":"27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings (Lecture Notes in Computer Science), Krzysztof Diks and Wojciech Rytter (Eds.)","volume":"2420","author":"Ku\u010dera Anton\u00edn","year":"2002"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.01.003"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542500"},{"key":"e_1_3_2_1_21_1","unstructured":"Christof L\u00f6ding. 2003. Infinite Graphs Generated by Tree Rewriting. Ph.D. Dissertation. RWTH Aachen University. Christof L\u00f6ding. 2003. Infinite Graphs Generated by Tree Rewriting. Ph.D. Dissertation. RWTH Aachen University."},{"key":"e_1_3_2_1_22_1","unstructured":"Richard Mayr. 1998. Decidability and Complexity of Model Checking Problems for Infinite State Systems. Ph.D. Dissertation. Technical University Munich Germany. Richard Mayr. 1998. Decidability and Complexity of Model Checking Problems for Infinite State Systems. Ph.D. Dissertation. Technical University Munich Germany."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00104-4"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90087-8"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-70918-3","volume-title":"FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 27th International Conference","author":"Reps Thomas W.","year":"2007"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2005.02.009"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700377256"},{"volume-title":"Automata, Languages and Programming, 29th International Colloquium, ICALP","year":"2002","author":"Srba Ji\u0159\u00ed","key":"e_1_3_2_1_28_1"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Ji\u0159\u00ed Srba. 2004. Roadmap of Infinite Results. Current Trends In Theoretical Computer Science The Challenge of the New Century Vol 2: Formal Models and Semantics (2004) 337--350. http:\/\/people.cs.aau.dk\/~srba\/roadmap\/ Ji\u0159\u00ed Srba. 2004. Roadmap of Infinite Results. Current Trends In Theoretical Computer Science The Challenge of the New Century Vol 2: Formal Models and Semantics (2004) 337--350. http:\/\/people.cs.aau.dk\/~srba\/roadmap\/","DOI":"10.1142\/9789812562494_0054"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90591-8"},{"key":"e_1_3_2_1_31_1","volume-title":"19th International Conference, CAV 2007, Berlin, Germany, July 3-7, 2007, Proceedings (Lecture Notes in Computer Science), Werner Damm and Holger Hermanns (Eds.)","volume":"4590","author":"Suwimonteerabuth Dejvuth","year":"2007"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321865"},{"volume-title":"B: Formal Models and Semantics. In van Leeuwen R@[33]. https:\/\/www.sciencedirect.com\/book\/9780444880741\/formal-models-and-semantics","year":"1990","author":"van Leeuwen Jan","key":"e_1_3_2_1_33_1"},{"volume-title":"30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015","year":"2015","author":"LICS","key":"e_1_3_2_1_34_1"}],"event":{"name":"LICS '20: 35th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society"],"location":"Saarbr\u00fccken Germany","acronym":"LICS '20"},"container-title":["Proceedings of the 35th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394827","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3373718.3394827","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:46Z","timestamp":1750200106000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394827"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,8]]},"references-count":34,"alternative-id":["10.1145\/3373718.3394827","10.1145\/3373718"],"URL":"https:\/\/doi.org\/10.1145\/3373718.3394827","relation":{},"subject":[],"published":{"date-parts":[[2020,7,8]]},"assertion":[{"value":"2020-07-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}