{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:59Z","timestamp":1750220579854,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,17]],"date-time":"2020-12-17T00:00:00Z","timestamp":1608163200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2021,1,31]]},"abstract":"<jats:p>We study alternating automata with qualitative semantics over infinite binary trees: Alternation means that two opposing players construct a decoration of the input tree called a run, and the qualitative semantics says that a run of the automaton is accepting if almost all branches of the run are accepting. In this article, we prove a positive and a negative result for the emptiness problem of alternating automata with qualitative semantics.<\/jats:p>\n          <jats:p>The positive result is the decidability of the emptiness problem for the case of B\u00fcchi acceptance condition. An interesting aspect of our approach is that we do not extend the classical solution for solving the emptiness problem of alternating automata, which first constructs an equivalent non-deterministic automaton. Instead, we directly construct an emptiness game making use of imperfect information.<\/jats:p>\n          <jats:p>The negative result is the undecidability of the emptiness problem for the case of co-B\u00fcchi acceptance condition. This result has two direct consequences: the undecidability of monadic second-order logic extended with the qualitative path-measure quantifier and the undecidability of the emptiness problem for alternating tree automata with non-zero semantics, a recently introduced probabilistic model of alternating tree automata.<\/jats:p>","DOI":"10.1145\/3431860","type":"journal-article","created":{"date-parts":[[2020,12,17]],"date-time":"2020-12-17T23:58:19Z","timestamp":1608249499000},"page":"1-24","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Alternating Tree Automata with Qualitative Semantics"],"prefix":"10.1145","volume":"22","author":[{"given":"Rapha\u00ebl","family":"Berthon","sequence":"first","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Belgium"}]},{"given":"Nathana\u00ebl","family":"Fijalkow","sequence":"additional","affiliation":[{"name":"CNRS 8 LaBRI, Talence, France"}]},{"given":"Emmanuel","family":"Filiot","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Belgium"}]},{"given":"Shibashis","family":"Guha","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Belgium"}]},{"given":"Bastien","family":"Maubert","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Napoli \u201cFederico II\u201d, Napoli, Italy"}]},{"given":"Aniello","family":"Murano","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Napoli \u201cFederico II\u201d, Napoli, Italy"}]},{"given":"Laureline","family":"Pinault","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Lyon, CNRS, ENS de Lyon, UCB Lyon 1, LIP, Lyon, France"}]},{"given":"Sophie","family":"Pinchinat","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Rennes, CNRS, IRISA, Rennes Cedex, France"}]},{"given":"Sasha","family":"Rubin","sequence":"additional","affiliation":[{"name":"University of Sydney, Darlington NSW, Australia"}]},{"given":"Olivier","family":"Serre","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Paris, IRIF, CNRS, Paris Cedex, France"}]}],"member":"320","published-online":{"date-parts":[[2020,12,17]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/2108242.2108243"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.5555\/1839560.1839562"},{"unstructured":"Rapha\u00ebl Berthon Emmanuel Filiot Shibashis Guha Bastien Maubert Nello Murano Laureline Pinault Jean-Fran\u00e7ois Raskin and Sasha Rubin. 2019. Monadic second-order logic with path-measure quantifier is undecidable. CoRR abs\/1901.04349.  Rapha\u00ebl Berthon Emmanuel Filiot Shibashis Guha Bastien Maubert Nello Murano Laureline Pinault Jean-Fran\u00e7ois Raskin and Sasha Rubin. 2019. Monadic second-order logic with path-measure quantifier is undecidable. CoRR abs\/1901.04349.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science. IEEE, 319--328","author":"Bertrand Nathalie","year":"2009","unstructured":"Nathalie Bertrand , Blaise Genest , and Hugo Gimbert . 2009 . Qualitative determinacy and decidability of stochastic games with signals . In Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science. IEEE, 319--328 . Nathalie Bertrand, Blaise Genest, and Hugo Gimbert. 2009. Qualitative determinacy and decidability of stochastic games with signals. In Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science. IEEE, 319--328."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (LIPIcs)","volume":"55","author":"Boja\u0144czyk Miko\u0142aj","year":"2016","unstructured":"Miko\u0142aj Boja\u0144czyk . 2016 . Thin MSO with a probabilistic path quantifier . In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (LIPIcs) , Vol. 55 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 96:1--96:13. Miko\u0142aj Boja\u0144czyk. 2016. Thin MSO with a probabilistic path quantifier. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (LIPIcs), Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 96:1--96:13."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (LIPIcs)","volume":"80","author":"Boja\u0144czyk Miko\u0142aj","year":"2017","unstructured":"Miko\u0142aj Boja\u0144czyk , Hugo Gimbert , and Edon Kelmendi . 2017 . Emptiness of zero automata is decidable . In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (LIPIcs) , Vol. 80 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 106:1--106:13. Miko\u0142aj Boja\u0144czyk, Hugo Gimbert, and Edon Kelmendi. 2017. Emptiness of zero automata is decidable. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (LIPIcs), Vol. 80. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 106:1--106:13."},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.5555\/3470152.3470213"},{"key":"e_1_2_1_8_1","article-title":"Randomization in automata on infinite trees","volume":"15","author":"Carayol Arnaud","year":"2014","unstructured":"Arnaud Carayol , Axel Haddad , and Olivier Serre . 2014 . Randomization in automata on infinite trees . ACM Trans. Comput. Logic 15 , 3 (2014), 24:1--24:33. Arnaud Carayol, Axel Haddad, and Olivier Serre. 2014. Randomization in automata on infinite trees. ACM Trans. Comput. Logic 15, 3 (2014), 24:1--24:33.","journal-title":"ACM Trans. Comput. Logic"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.3233\/FI-2018-1687"},{"key":"e_1_2_1_10_1","article-title":"Partial-observation stochastic games: How to win when belief fails","volume":"15","author":"Chatterjee Krishnendu","year":"2014","unstructured":"Krishnendu Chatterjee and Laurent Doyen . 2014 . Partial-observation stochastic games: How to win when belief fails . ACM Trans. Comput. Logic 15 , 2 (2014), 16:1--16:44. Krishnendu Chatterjee and Laurent Doyen. 2014. Partial-observation stochastic games: How to win when belief fails. ACM Trans. Comput. Logic 15, 2 (2014), 16:1--16:44.","journal-title":"ACM Trans. Comput. Logic"},{"key":"e_1_2_1_11_1","volume-title":"Algorithms for omega-regular games with imperfect information. Logic. Methods Comput. Sci. 3, 3","author":"Chatterjee Krishnendu","year":"2007","unstructured":"Krishnendu Chatterjee , Laurent Doyen , Thomas A. Henzinger , and Jean-Fran\u00e7ois Raskin . 2007. Algorithms for omega-regular games with imperfect information. Logic. Methods Comput. Sci. 3, 3 ( 2007 ). Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, and Jean-Fran\u00e7ois Raskin. 2007. Algorithms for omega-regular games with imperfect information. Logic. Methods Comput. Sci. 3, 3 (2007)."},{"key":"e_1_2_1_12_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 17th International Colloquium on Automata, Languages, and Programming (ICALP'90)","author":"Courcoubetis Costas","unstructured":"Costas Courcoubetis and Mihalis Yannakakis . 1990. Markov decision processes and regular events (extended abstract) . In Proceedings of the 17th International Colloquium on Automata, Languages, and Programming (ICALP'90) , Lecture Notes in Computer Science , Vol. 443 . Springer , 336--349. Costas Courcoubetis and Mihalis Yannakakis. 1990. Markov decision processes and regular events (extended abstract). In Proceedings of the 17th International Colloquium on Automata, Languages, and Programming (ICALP'90), Lecture Notes in Computer Science, Vol. 443. Springer, 336--349."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 2nd International Workshop on Probabilistic Methods in Verification. 19--32","author":"de Alfaro Luca","year":"1999","unstructured":"Luca de Alfaro . 1999 . The verification of probabilistic systems under memoryless partial-information policies is hard . In Proceedings of the 2nd International Workshop on Probabilistic Methods in Verification. 19--32 . Luca de Alfaro. 1999. The verification of probabilistic systems under memoryless partial-information policies is hard. In Proceedings of the 2nd International Workshop on Probabilistic Methods in Verification. 19--32."},{"key":"e_1_2_1_14_1","volume-title":"Vardi","author":"Fagin Ronald","year":"1995","unstructured":"Ronald Fagin , Joseph Y. Halpern , Yoram. Moses, and Moshe Y . Vardi . 1995 . Reasoning about Knowledge. MIT Press . Ronald Fagin, Joseph Y. Halpern, Yoram. Moses, and Moshe Y. Vardi. 1995. Reasoning about Knowledge. MIT Press."},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/3157831.3157833"},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"Deciding the value 1 problem for probabilistic leaktight automata","volume":"11","author":"Fijalkow Nathana\u00ebl","year":"2015","unstructured":"Nathana\u00ebl Fijalkow , Hugo Gimbert , Edon Kelmendi , and Youssouf Oualhadj . 2015 . Deciding the value 1 problem for probabilistic leaktight automata . Logic. Methods Comput. Sci. 11 , 2 (2015), 1 -- 42 . Nathana\u00ebl Fijalkow, Hugo Gimbert, Edon Kelmendi, and Youssouf Oualhadj. 2015. Deciding the value 1 problem for probabilistic leaktight automata. Logic. Methods Comput. Sci. 11, 2 (2015), 1--42.","journal-title":"Logic. Methods Comput. Sci."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (LIPIcs)","volume":"24","author":"Fijalkow Nathana\u00ebl","year":"2013","unstructured":"Nathana\u00ebl Fijalkow , Sophie Pinchinat , and Olivier Serre . 2013 . Emptiness of alternating tree automata using games with imperfect information . In Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (LIPIcs) , Vol. 24 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 299--311. Nathana\u00ebl Fijalkow, Sophie Pinchinat, and Olivier Serre. 2013. Emptiness of alternating tree automata using games with imperfect information. In Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (LIPIcs), Vol. 24. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 299--311."},{"unstructured":"Nathana\u00ebl Fijalkow Sophie Pinchinat and Olivier Serre. 2013. Emptiness of Alternating Tree Automata Using Games with Imperfect Information. Retrieved from https:\/\/2.zoppoz.workers.dev:443\/https\/hal.inria.fr\/hal-01260682.  Nathana\u00ebl Fijalkow Sophie Pinchinat and Olivier Serre. 2013. Emptiness of Alternating Tree Automata Using Games with Imperfect Information. Retrieved from https:\/\/2.zoppoz.workers.dev:443\/https\/hal.inria.fr\/hal-01260682.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 29th International Conference on Concurrency Theory (LIPIcs)","volume":"118","author":"Fournier Paulin","year":"2018","unstructured":"Paulin Fournier and Hugo Gimbert . 2018 . Alternating nonzero automata . In Proceedings of the 29th International Conference on Concurrency Theory (LIPIcs) , Vol. 118 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 13:1--13:16. Paulin Fournier and Hugo Gimbert. 2018. Alternating nonzero automata. In Proceedings of the 29th International Conference on Concurrency Theory (LIPIcs), Vol. 118. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 13:1--13:16."},{"key":"e_1_2_1_20_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 37th International Colloquium on Automata, Languages and Programming","author":"Gimbert Hugo","unstructured":"Hugo Gimbert and Youssouf Oualhadj . 2010. Probabilistic automata on finite words: Decidable and undecidable problems . In Proceedings of the 37th International Colloquium on Automata, Languages and Programming , Lecture Notes in Computer Science , Vol. 6199 . Springer , 527--538. Hugo Gimbert and Youssouf Oualhadj. 2010. Probabilistic automata on finite words: Decidable and undecidable problems. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 6199. Springer, 527--538."},{"key":"e_1_2_1_21_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 34th International Colloquium on Automata, Languages, and Programming","author":"Gimbert Hugo","unstructured":"Hugo Gimbert and Wies\u0142aw Zielonka . 2007. Perfect information stochastic priority games . In Proceedings of the 34th International Colloquium on Automata, Languages, and Programming , Lecture Notes in Computer Science , Vol. 4596 . Springer , 850--861. Hugo Gimbert and Wies\u0142aw Zielonka. 2007. Perfect information stochastic priority games. In Proceedings of the 34th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 4596. Springer, 850--861."},{"key":"e_1_2_1_22_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 36th International Colloquium on Automata, Languages, and Programming","author":"Gripon Vincent","unstructured":"Vincent Gripon and Olivier Serre . 2009. Qualitative concurrent stochastic games with imperfect information . In Proceedings of the 36th International Colloquium on Automata, Languages, and Programming , Lecture Notes in Computer Science , Vol. 5556 . Springer , 200--211. Vincent Gripon and Olivier Serre. 2009. Qualitative concurrent stochastic games with imperfect information. In Proceedings of the 36th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 5556. Springer, 200--211."},{"volume-title":"Lectures in Game Theory for Computer Scientists, Krzysztof R","author":"Ku\u010dera Anton\u00edn","unstructured":"Anton\u00edn Ku\u010dera . 2011. Turn-based stochastic games . In Lectures in Game Theory for Computer Scientists, Krzysztof R . Apt and Erich Grdel (Eds.). Cambridge University Press , New York, NY , Chapter 5, 146--184. Anton\u00edn Ku\u010dera. 2011. Turn-based stochastic games. In Lectures in Game Theory for Computer Scientists, Krzysztof R. Apt and Erich Grdel (Eds.). Cambridge University Press, New York, NY, Chapter 5, 146--184.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the International Symposium on Logical Foundations of Computer Science","author":"Michalewski Henryk","unstructured":"Henryk Michalewski and Matteo Mio . 2016. Measure quantifier in monadic second order logic . In Proceedings of the International Symposium on Logical Foundations of Computer Science , Lecture Notes in Computer Science , Vol. 9537 . Springer , 267--282. Henryk Michalewski and Matteo Mio. 2016. Measure quantifier in monadic second order logic. In Proceedings of the International Symposium on Logical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 9537. Springer, 267--282."},{"key":"e_1_2_1_25_1","volume-title":"Monadic second order logic with measure and category quantifiers. Logic. Methods Comput. Sci. 14, 2","author":"Mio Matteo","year":"2018","unstructured":"Matteo Mio , Micha\u0142 Skrzypczak , and Henryk Michalewski . 2018. Monadic second order logic with measure and category quantifiers. Logic. Methods Comput. Sci. 14, 2 ( 2018 ). Matteo Mio, Micha\u0142 Skrzypczak, and Henryk Michalewski. 2018. Monadic second order logic with measure and category quantifiers. Logic. Methods Comput. Sci. 14, 2 (2018)."},{"volume-title":"Introduction to Probabilistic Automata","author":"Paz Azaria","unstructured":"Azaria Paz . 1971. Introduction to Probabilistic Automata . Academic Press . Azaria Paz. 1971. Introduction to Probabilistic Automata. Academic Press.","key":"e_1_2_1_26_1"},{"volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"Puterman Martin L.","unstructured":"Martin L. Puterman . 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming . John Wiley 8 Sons, Inc., New York, NY. Martin L. Puterman. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley 8 Sons, Inc., New York, NY.","key":"e_1_2_1_27_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1016\/S0019-9958(63)90290-0"},{"key":"e_1_2_1_29_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 . Trans. AMS 141 (1969), 1 -- 35 . https:\/\/2.zoppoz.workers.dev:443\/https\/www.ams.org\/journals\/tran\/1969-141-00\/S0002-9947-1969-0246760-1\/. Michael O. Rabin. 1969. Decidability of second-order theories and automata on infinite trees. Trans. AMS 141 (1969), 1--35. https:\/\/2.zoppoz.workers.dev:443\/https\/www.ams.org\/journals\/tran\/1969-141-00\/S0002-9947-1969-0246760-1\/.","journal-title":"Trans. AMS"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201979)","author":"Reif J. H.","year":"1979","unstructured":"J. H. Reif . 1979 . Universal games of incomplete information . In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201979) . ACM, 288--308. J. H. Reif. 1979. Universal games of incomplete information. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201979). ACM, 288--308."},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1016\/0022-0000(84)90034-5"},{"volume-title":"Handbook of Formal Language Theory","author":"Thomas Wolfgang","unstructured":"Wolfgang Thomas . 1997. Languages , automata, and logic . In Handbook of Formal Language Theory , G. Rozenberg and A. Salomaa (Eds.). Vol. III . 389--455. Wolfgang Thomas. 1997. Languages, automata, and logic. In Handbook of Formal Language Theory, G. Rozenberg and A. Salomaa (Eds.). Vol. III. 389--455.","key":"e_1_2_1_32_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1016\/S0304-3975(98)00009-7"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3431860","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3431860","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:31Z","timestamp":1750195891000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3431860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,17]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1,31]]}},"alternative-id":["10.1145\/3431860"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/3431860","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2020,12,17]]},"assertion":[{"value":"2020-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}