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)
68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Related Items
Unnamed Item, On the Way to Alternating Weak Automata, A Characterisation of Pi^0_2 Regular Tree Languages, Erratum for “Randomization in Automata on Infinite Trees”, Index Problems for Game Automata, Polishness of some topologies related to word or tree automata, An upper bound on the complexity of recognizable tree languages, Regular languages of thin trees, \(\varSigma^{\mu}_2\) is decidable for \(\varPi^{\mu}_2\), Wadge-Wagner hierarchies, Unambiguous Büchi Is Weak, On the Weak Index Problem for Game Automata, Cardinality Quantifiers in MLO over Trees, Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
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