LIPIcs.STACS.2012.396.pdf
- Filesize: 0.65 MB
- 12 pages
Document
On the separation question for tree languages
Authors
-
Part of:
Volume:
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2012-02-24
Cite As Get BibTex
André Arnold, Henryk Michalewski, and Damian Niwinski. On the separation question for tree languages. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 396-407, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.STACS.2012.396
Abstract
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.
Subject Classification
Keywords
- Alternating automata on infinite trees
- Index hierarchy
- Separation property
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads