The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata

DOI10.1007/978-3-540-70583-3_33MaRDI QIDQ3519517zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

decidabilityguidable automatainfinite treesMostowski hierarchysemantic gamestree automata

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Applications of model theory (03C98) Computability and recursion theory (03D99) Formal languages and automata (68Q45)

Recommendations

• Automata on infinite trees with equality and disequality constraints between siblings
• The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem
• Topological characterizations of infinite tree languages
• Uniform inevitability is tree automaton ineffable
• scientific article; zbMATH DE number 3982544
• A tentative approach for the Wadge-Wagner hierarchy of regular tree languages of index \([0,2]\)
• Descriptive set theoretic methods in automata theory. Decidability and topological complexity
• Counting branches in trees using games
• On Guidable Index of Tree Automata

Cites work

• Algorithms for determining relative star height and star height
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Distance desert automata and the star height problem
• scientific article; zbMATH DE number 1670861 (Why is no real title available?)
• scientific article; zbMATH DE number 3960988 (Why is no real title available?)
• scientific article; zbMATH DE number 3990873 (Why is no real title available?)
• scientific article; zbMATH DE number 3591916 (Why is no real title available?)
• scientific article; zbMATH DE number 1136080 (Why is no real title available?)
• scientific article; zbMATH DE number 2102739 (Why is no real title available?)
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• MSO on the Infinite Binary Tree: Choice and Order
• On the topological complexity of tree languages
• Progress measures, immediate determinacy, and a subset construction for tree automata
• The modal mu-calculus alternation hierarchy is strict
• Theμ-calculus alternation-depth hierarchy is strict on binary trees

Cited in

(23)

• \(\varSigma^{\mu}_2\) is decidable for \(\varPi^{\mu}_2\)
• Automata on infinite trees
• Stamina: stabilisation monoids in automata theory
• The descriptive complexity of modal model-checking games
• Trading bounds for memory in games with counters
• The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem
• R-Automata
• scientific article; zbMATH DE number 5485222 (Why is no real title available?)
• Topological extension of parity automata
• Disjunctive form and the modal alternation hierarchy
• A Characterisation of Pi^0_2 Regular Tree Languages
• Universality of R-automata with Value Copying
• Monoidal-closed categories of tree automata
• Regular tree languages in low levels of the Wadge hierarchy
• Index problems for game automata
• Weak MSO with the unbounding quantifier
• Cost Automata, Safe Schemes, and Downward Closures
• From Muller to parity and Rabin qutomata: optimal transformations preserving (history) determinism
• Cost automata, safe schemes, and downward closures
• History-determinism vs fair simulation
• Deterministic and game separability for regular languages of infinite trees
• A dichotomy theorem for ordinal ranks in MSO
• A dichotomy theorem for ordinal ranks in MSO

This page was built for publication: The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3519517)