2026-07-23T13:21:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3415 2024-03-06T10:34:12Z ddc:004 open_access

On the separation question for tree languages Arnold, André Michalewski, Henryk Niwinski, Damian Alternating automata on infinite trees Index hierarchy Separation property We show that the separation property fails for the classes Sigma_n of the Rabin-Mostowski index hierarchy of alternating automata on infinite trees. This extends our previous result (obtained with Szczepan Hummel) on the failure of the separation property for the class Sigma_2 (i.e., for co-Buchi sets). It remains open whether the separation property does hold for the classes Pi_n of the index hierarchy. To prove our result, we first consider the Rabin-Mostowski index hierarchy of deterministic automata on infinite words, for which we give a complete answer (generalizing previous results of Selivanov): the separation property holds for Pi_n and fails for Sigma_n-classes. The construction invented for words turns out to be useful for trees via a suitable game. Schloss Dagstuhl – Leibniz-Zentrum für Informatik André Arnold and Henryk Michalewski and Damian Niwinski 2012 Is Part Of LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2012.396 urn:nbn:de:0030-drops-34156 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.396 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode