License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.56
URN: urn:nbn:de:0030-drops-80683
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8068/
Cavallari, Filippo ;
Michalewski, Henryk ;
Skrzypczak, Michal
A Characterisation of Pi^0_2 Regular Tree Languages
Abstract
We show an algorithm that for a given regular tree language L decides if L is in Pi^0_2, that is if L belongs to the second level of Borel Hierarchy. Moreover, if L is in Pi^0_2, then we construct a weak alternating automaton of index (0, 2) which recognises L. We also prove that for a given language L, L is recognisable by a weak alternating (1, 3)-automaton if and only if it is recognisable by a weak non-deterministic (1, 3)-automaton.
BibTeX - Entry
@InProceedings{cavallari_et_al:LIPIcs:2017:8068,
author = {Filippo Cavallari and Henryk Michalewski and Michal Skrzypczak},
title = {{A Characterisation of Pi^0_2 Regular Tree Languages}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {56:1--56:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-046-0},
ISSN = {1868-8969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8068},
URN = {urn:nbn:de:0030-drops-80683},
doi = {10.4230/LIPIcs.MFCS.2017.56},
annote = {Keywords: infinite trees, Rabin-Mostowski hierarchy, regular languages}
}
|
Keywords: |
|
infinite trees, Rabin-Mostowski hierarchy, regular languages |
|
Collection: |
|
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.12.2017 |
