{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T11:01:46Z","timestamp":1780743706749,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","funder":[{"name":"Agence Nationale de la Recherche","award":["ANR-23-CE48-0008"],"award-info":[{"award-number":["ANR-23-CE48-0008"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718310","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"1839-1850","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1171-8790","authenticated-orcid":false,"given":"Karoliina","family":"Lehtinen","sequence":"first","affiliation":[{"name":"CNRS, Aix-Marseille Universit\u00e9, Marseille, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2404-0707","authenticated-orcid":false,"given":"Aditya","family":"Prakash","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-18(3:16)2022"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2024.124"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-53291-8_28"},{"key":"e_1_3_2_1_4_1","volume-title":"Polynomial time algorithms for inclusion and equivalence of deterministic omega acceptors. CoRR, abs\/2002.03191","author":"Angluin Dana","year":"2020","unstructured":"Dana Angluin and Dana Fisman. 2020. Polynomial time algorithms for inclusion and equivalence of deterministic omega acceptors. CoRR, abs\/2002.03191 (2020), arxiv:2002.03191"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.FSTTCS.2018.16"},{"key":"e_1_3_2_1_6_1","unstructured":"Udi Boker Denis Kuperberg Karoliina Lehtinen and Micha\u0142 Skrzypczak. 2020. On Succinctness and Recognisability of Alternating Good-for-Games Automata. arXiv arxiv:2002.07278"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.FSTTCS.2017.18"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.FSTTCS.2021.38"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.46298\/LMCS-19(4:8)2023"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584676.3584682"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.46298\/LMCS-20(4:1)2024"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CONCUR.2023.18"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273681"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1145288"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2022.12"},{"key":"e_1_3_2_1_16_1","unstructured":"Antonio Casares. 2023. Structural properties of automata over infinite words and memory for games (Propri\u00e9t\u00e9s structurelles des automates sur les mots infinis et m\u00e9moire pour les jeux). Ph. D. Dissertation. Universit\u00e9 de Bordeaux France. https:\/\/theses.hal.science\/tel-04314678"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2021.123"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.117"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CSL.2025.22"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71389-0_12"},{"key":"e_1_3_2_1_21_1","first-page":"3","article-title":"Application of recursive arithmetic to the problem of circuit synthesis","volume":"1","author":"Church Alonzo","year":"1957","unstructured":"Alonzo Church. 1957. Application of recursive arithmetic to the problem of circuit synthesis. Summaries of the Summer Institute of Symbolic Logic, 1 (1957), 3\u201350.","journal-title":"Summaries of the Summer Institute of Symbolic Logic"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10575-8"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1997.614939"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.FSTTCS.2022.36"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-15648-8_7"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2305.10546"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Shibashis Guha Isma\u00ebl Jecker Karoliina Lehtinen and Martin Zimmermann. 2022. A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct. https:\/\/doi.org\/10.48550\/ARXIV.2105.02611 10.48550\/ARXIV.2105.02611","DOI":"10.48550\/ARXIV.2105.02611"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","unstructured":"Yuri Gurevich and Leo Harrington. 1982. Trees Automata and Games. In STOC. ACM 60\u201365. https:\/\/doi.org\/10.1145\/800070.802177 10.1145\/800070.802177","DOI":"10.1145\/800070.802177"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CSL.2023.24"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3085"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_26"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_43"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46541-3_24"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_24"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Karoliina Lehtinen and Martin Zimmermann. 2020. Good-for-games \u03c9 -Pushdown Automata. In LICS20. 689\u2013702.","DOI":"10.1145\/3373718.3394737"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-18(1:3)2022"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","unstructured":"Amir Pnueli. 1977. The Temporal Logic of Programs. In FOCS. 46\u201357. https:\/\/doi.org\/10.1109\/SFCS.1977.32 10.1109\/SFCS.1977.32","DOI":"10.1109\/SFCS.1977.32"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Amir Pnueli and Roni Rosner. 1989. On the Synthesis of a Reactive Module. In POPL. 179\u2013190. https:\/\/doi.org\/10.1145\/75277.75293 10.1145\/75277.75293","DOI":"10.1145\/75277.75293"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-57228-9_11"},{"key":"e_1_3_2_1_40_1","volume-title":"History-Deterministic Parity Automata: Games, Complexity, and the 2-Token Theorem. Ph. D. Dissertation","author":"Prakash Aditya","unstructured":"Aditya Prakash. 2025. History-Deterministic Parity Automata: Games, Complexity, and the 2-Token Theorem. Ph. D. Dissertation. University of Warwick. arxiv:2501.12302"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30829-1_11"},{"key":"e_1_3_2_1_42_1","first-page":"1","article-title":"Decidability of Second-Order Theories and Automata on Infinite Trees","volume":"141","author":"Rabin Michael O.","year":"1969","unstructured":"Michael O. Rabin. 1969. Decidability of Second-Order Theories and Automata on Infinite Trees. Transactions of the American Mathematical Society, 141 (1969), 1\u201335. issn:00029947 http:\/\/www.jstor.org\/stable\/1995086","journal-title":"Transactions of the American Mathematical Society"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2019.100"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90031-X"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00185-2"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718310","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:50:29Z","timestamp":1750693829000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718310"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":45,"alternative-id":["10.1145\/3717823.3718310","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718310","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}