The Wadge Hierarchy of Deterministic Tree Languages
From MaRDI portal
Abstract: We provide a complete description of the Wadge hierarchy for deterministically recognisable sets of infinite trees. In particular we give an elementary procedure to decide if one deterministic tree language is continuously reducible to another. This extends Wagner's results on the hierarchy of omega-regular languages of words to the case of trees.
Recommendations
Cited in
(14)- A hierarchy of deterministic context-free \(\omega\)-languages.
- Wadge-Wagner hierarchies
- Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
- Regular tree languages in low levels of the Wadge hierarchy
- Polishness of some topologies related to word or tree automata
- Computer Science Logic
- On the length of the Wadge hierarchy of -context-free languages
- On the Topological Complexity of Weakly Recognizable Tree Languages
- Continuous separation of game languages
- A tentative approach for the Wadge-Wagner hierarchy of regular tree languages of index \([0,2]\)
- An upper bound on the complexity of recognizable tree languages
- The Wadge Hierarchy of Deterministic Tree Languages
- Extending Wagner's hierarchy to deterministic visibly pushdown automata
- Fine hierarchies and m-reducibilities in theoretical computer science
This page was built for publication: The Wadge Hierarchy of Deterministic Tree Languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5901224)
