Mikołaj Bojańczyk ; Filippo Cavallari ; Thomas Place ; Michał Skrzypczak - Regular tree languages in low levels of the Wadge Hierarchy

lmcs:4647 - Logical Methods in Computer Science, September 4, 2019, Volume 15, Issue 3 - https://doi.org/10.23638/LMCS-15(3:27)2019
Regular tree languages in low levels of the Wadge HierarchyArticle

Authors: Mikołaj Bojańczyk ; Filippo Cavallari ; Thomas Place ; Michał Skrzypczak

    In this article we provide effective characterisations of regular languages of infinite trees that belong to the low levels of the Wadge hierarchy. More precisely we prove decidability for each of the finite levels of the hierarchy; for the class of the Boolean combinations of open sets $BC(\Sigma_1^0)$ (i.e. the union of the first $\omega$ levels); and for the Borel class $\Delta_2^0$ (i.e. for the union of the first $\omega_1$ levels).


    Volume: Volume 15, Issue 3
    Published on: September 4, 2019
    Accepted on: June 18, 2019
    Submitted on: June 26, 2018
    Keywords: Computer Science - Formal Languages and Automata Theory

    Consultation statistics

    This page has been seen 1587 times.
    This article's PDF has been downloaded 230 times.