A gap property of deterministic tree languages.
From MaRDI portal
Publication:1401364
DOI10.1016/S0304-3975(02)00452-8zbMath1044.68120MaRDI QIDQ1401364
Igor Walukiewicz, Damian Niwinski
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (14)
Erratum for “Randomization in Automata on Infinite Trees” ⋮ Index Problems for Game Automata ⋮ Regular languages of thin trees ⋮ Unnamed Item ⋮ On the Weak Index Problem for Game Automata ⋮ \(\varSigma^{\mu}_2\) is decidable for \(\varPi^{\mu}_2\) ⋮ Polishness of some topologies related to word or tree automata ⋮ Unambiguous Büchi Is Weak ⋮ On the Way to Alternating Weak Automata ⋮ Cardinality Quantifiers in MLO over Trees ⋮ Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata ⋮ Wadge-Wagner hierarchies ⋮ A Characterisation of Pi^0_2 Regular Tree Languages ⋮ An upper bound on the complexity of recognizable tree languages
Cites Work
- Computing the rabin index of a regular language of infinite words
- Hierarchies of weak automata and weak monadic formulas
- Alternating automata on infinite trees
- The Borel hierarchy is infinite in the class of regular sets of trees
- The modal mu-calculus alternation hierarchy is strict
- Topology and descriptive set theory
- Deciding Equivalence of Finite Tree Automata
- Theμ-calculus alternation-depth hierarchy is strict on binary trees
- Computing the Rabin Index of a Parity Automaton
- Testing and generating infinite sequences by a finite automaton
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Rudiments of \(\mu\)-calculus
- On model checking for the \(\mu\)-calculus and its fragments
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A gap property of deterministic tree languages.
