The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
From MaRDI portal
Publication:3519517
DOI10.1007/978-3-540-70583-3_33zbMath1165.68038OpenAlexW1528015591MaRDI QIDQ3519517
Thomas Colcombet, Christof Löding
Publication date: 19 August 2008
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-70583-3_33
Formal languages and automata (68Q45) Model theory of finite structures (03C13) Computability and recursion theory (03D99) Applications of model theory (03C98)
Related Items (15)
Index Problems for Game Automata ⋮ Trading Bounds for Memory in Games with Counters ⋮ Stamina: stabilisation monoids in automata theory ⋮ Unnamed Item ⋮ Cost Automata, Safe Schemes, and Downward Closures ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem ⋮ R-Automata ⋮ Weak MSO with the unbounding quantifier ⋮ \(\varSigma^{\mu}_2\) is decidable for \(\varPi^{\mu}_2\) ⋮ Universality of R-automata with Value Copying ⋮ Monoidal-closed categories of tree automata ⋮ Automata on infinite trees ⋮ A Characterisation of Pi^0_2 Regular Tree Languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms for determining relative star height and star height
- The modal mu-calculus alternation hierarchy is strict
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Progress measures, immediate determinacy, and a subset construction for tree automata
- MSO on the Infinite Binary Tree: Choice and Order
- Theμ-calculus alternation-depth hierarchy is strict on binary trees
- Distance desert automata and the star height problem
- Decidability of Second-Order Theories and Automata on Infinite Trees
This page was built for publication: The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
