Theμ-calculus alternation-depth hierarchy is strict on binary trees
From MaRDI portal
Publication:4943546
DOI10.1051/ita:1999121zbMath0945.68118OpenAlexW2126399192MaRDI QIDQ4943546
Publication date: 3 October 2000
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/222087
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)
Related Items (28)
Index Problems for Game Automata ⋮ The mu-calculus and Model Checking ⋮ The \(\mu\)-calculus alternation depth hierarchy is infinite over finite planar graphs ⋮ Measure Properties of Game Tree Languages ⋮ Measure properties of regular sets of trees ⋮ On the \(\mu \)-calculus over transitive and finite transitive frames ⋮ On the equational definition of the least prefixed point. ⋮ A gap property of deterministic tree languages. ⋮ The alternation hierarchy of the \(\mu \)-calculus over weakly transitive frames ⋮ Unnamed Item ⋮ The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Descriptive Complexity of Parity Games ⋮ The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity ⋮ Deciding low levels of tree-automata hierarchy ⋮ On the separation question for tree languages ⋮ Monadic Second Order Logic And Its Fragments ⋮ \(\varSigma^{\mu}_2\) is decidable for \(\varPi^{\mu}_2\) ⋮ Ambiguous classes in \(\mu\)-calculi hierarchies ⋮ Fixpoint alternation: arithmetic, transition systems, and the binary tree ⋮ On Distributive Fixed-Point Expressions ⋮ On the Strength of Unambiguous Tree Automata ⋮ The alternation hierarchy in fixpoint logic with chop is strict too ⋮ Unambiguous Büchi Is Weak ⋮ Monoidal-closed categories of tree automata ⋮ Domain mu-calculus ⋮ Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
Cites Work
- Hierarchies of weak automata and weak monadic formulas
- Alternating automata on infinite trees
- Logical definability of fixed points
- Alternating automata, the weak monadic theory of trees and its complexity
- Fixed point characterization of infinite behavior of finite-state systems
- Monadic second order logic on tree-like structures
- Fixpoint alternation: arithmetic, transition systems, and the binary tree
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Theμ-calculus alternation-depth hierarchy is strict on binary trees
