2026-07-25T02:55:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8068 2024-03-06T10:40:56Z ddc:004 open_access

A Characterisation of Pi^0_2 Regular Tree Languages Cavallari, Filippo Michalewski, Henryk Skrzypczak, Michal infinite trees Rabin-Mostowski hierarchy regular languages 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Filippo Cavallari and Henryk Michalewski and Michal Skrzypczak 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.56 urn:nbn:de:0030-drops-80683 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.56 eng https://creativecommons.org/licenses/by/3.0/legalcode