{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:13:01Z","timestamp":1750306381654,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,11,2]],"date-time":"2016-11-02T00:00:00Z","timestamp":1478044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Poland\u2019s National Science Center","award":["DEC-2012\/05\/N\/ST6\/03254"],"award-info":[{"award-number":["DEC-2012\/05\/N\/ST6\/03254"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2016,11,15]]},"abstract":"<jats:p>For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognize this language with a nondeterministic, alternating, or weak alternating parity automaton. These questions are known as, respectively, the nondeterministic, alternating, and weak Rabin-Mostowski index problems. Whether they can be answered effectively is a long-standing open problem, solved so far only for languages recognizable by deterministic automata (the alternating variant trivializes).<\/jats:p>\n          <jats:p>We investigate a wider class of regular languages, recognizable by so-called game automata, which can be seen as the closure of deterministic ones under complementation and composition. Game automata are known to recognize languages arbitrarily high in the alternating Rabin-Mostowski index hierarchy; that is, the alternating index problem does not trivialize anymore.<\/jats:p>\n          <jats:p>Our main contribution is that all three index problems are decidable for languages recognizable by game automata. Additionally, we show that it is decidable whether a given regular language can be recognized by a game automaton.<\/jats:p>","DOI":"10.1145\/2946800","type":"journal-article","created":{"date-parts":[[2016,11,4]],"date-time":"2016-11-04T12:49:04Z","timestamp":1478263744000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Index Problems for Game Automata"],"prefix":"10.1145","volume":"17","author":[{"given":"Alessandro","family":"Facchini","sequence":"first","affiliation":[{"name":"IDSIA, Switzerlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Filip","family":"Murlak","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warszawa, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Skrzypczak","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warszawa, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,11,2]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"329","article-title":"The mu-calculus alternation-depth hierarchy is strict on binary trees","volume":"33","author":"Arnold Andr\u00e9","year":"1999","journal-title":"ITA"},{"key":"e_1_2_1_2_1","unstructured":"Andr\u00e9 Arnold and Damian Niwi\u0144ski. 2001. Rudiments of Mu-Calculus. Elsevier.  Andr\u00e9 Arnold and Damian Niwi\u0144ski. 2001. Rudiments of Mu-Calculus. Elsevier."},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"Continuous separation of game languages","volume":"81","author":"Arnold Andr\u00e9","year":"2007","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.024"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_13"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/646513.695641"},{"volume-title":"Proceedings of the 1960 International Congress for Logic, Methodology and Philosophy of Science. 1--11","year":"1962","author":"B\u00fcchi Julius Richard","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the 22nd EACLS Annual Conference (CSL\u201913)","year":"2013","author":"Colcombet Thomas","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_33"},{"volume-title":"Proceedings of the 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201911)","year":"2011","author":"Duparc Jacques","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2391495.2391520"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185392"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2013.56"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47709-0_8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Alexander Kechris. 1995. Classical Descriptive Set Theory. Springer-Verlag New York.  Alexander Kechris. 1995. Classical Descriptive Set Theory. Springer-Verlag New York.","DOI":"10.1007\/978-1-4612-4190-4"},{"key":"e_1_2_1_16_1","unstructured":"Denis Kuperberg. 2012. Etude de Classes de Fonctions de Co\u00fbt R\u00e9guli\u00e8res. Ph.D. Dissertation. Universit\u00e9 Paris Diderot.  Denis Kuperberg. 2012. Etude de Classes de Fonctions de Co\u00fbt R\u00e9guli\u00e8res. Ph.D. Dissertation. Universit\u00e9 Paris Diderot."},{"volume-title":"Proceedings of the 22nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201902)","year":"2002","author":"K\u00fcsters Ralf","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80013-X"},{"volume-title":"Proceedings of the Fifth Symposium on Computation Theory. 157--168","year":"1984","author":"Mostowski Andrzej W.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90283-8"},{"volume-title":"Proceedings of the 13th International Colloquium on Automata, Languages and Programming (ICALP\u201986)","author":"Muller David E.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538363_30"},{"key":"e_1_2_1_24_1","unstructured":"Filip Murlak. 2008a. Effective Topological Hierarchies of Recognizable Tree Languages. Ph.D. Dissertation. University of Warsaw.  Filip Murlak. 2008a. Effective Topological Hierarchies of Recognizable Tree Languages. Ph.D. Dissertation. University of Warsaw."},{"volume-title":"Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201908)","year":"2008","author":"Murlak Filip","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/646513.695664"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00452-8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2772082.2772281"},{"volume-title":"Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201999)","year":"1999","author":"Otto Martin","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"141","author":"Rabin Michael O.","year":"1969","journal-title":"Trans. of the American Math. Soc."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71929-3"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.2307\/1971037"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90030-W"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/646253.683944"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Michael Vanden Boom. 2012. Weak Cost Automata over Infinite Trees. Ph.D. Dissertation. University of Oxford.  Michael Vanden Boom. 2012. Weak Cost Automata over Infinite Trees. Ph.D. Dissertation. University of Oxford.","DOI":"10.1007\/978-3-642-22993-0_52"},{"key":"e_1_2_1_36_1","unstructured":"William Wadge. 1983. Reducibility and Determinateness in the Baire Space. Ph.D. Dissertation. University of California Berkeley.   William Wadge. 1983. Reducibility and Determinateness in the Baire Space. Ph.D. Dissertation. University of California Berkeley."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)80541-3"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2946800","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2946800","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:02Z","timestamp":1750223222000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2946800"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,2]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11,15]]}},"alternative-id":["10.1145\/2946800"],"URL":"https:\/\/doi.org\/10.1145\/2946800","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2016,11,2]]},"assertion":[{"value":"2015-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}