文章基本信息

标题：On the separation question for tree languages
本地全文：下载
作者：Andr{\'e} Arnold ; Henryk Michalewski ; Damian Niwinski 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：14
页码：396-407
DOI：10.4230/LIPIcs.STACS.2012.396
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Alternating automata on infinite trees; Index hierarchy; Separation property