A gap property of deterministic tree languages.

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)

zbMATH Keywords

weak alternating automata

Mathematics Subject Classification ID

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Related Items

Erratum for “Randomization in Automata on Infinite Trees”, Index Problems for Game 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\), 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