Deciding the Borel complexity of regular tree languages

2014 
We show that it is decidable whether a given a regular tree language belongs to the class ${\bf \Delta^0_2}$ of the Borel hierarchy, or equivalently whether the Wadge degree of a regular tree language is countable.
    • Correction
    • Cite
    • Save
    • Machine Reading By IdeaReader
    6
    References
    1
    Citations
    NaN
    KQI
    []