Deciding low levels of tree-automata hierarchy

DOI10.1016/S1571-0661(04)80541-3zbMath1261.68082MaRDI QIDQ4916202

Igor Walukiewicz

Publication date: 19 April 2013

Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

finite automatamu-calculusfixpointquantifier hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Index Problems for Game Automata ⋮ Unnamed Item ⋮ Characterizing EF and EX tree logics ⋮ The uniform measure of simple regular sets of infinite trees ⋮ Automata on infinite trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the rabin index of a regular language of infinite words
• Alternating automata on infinite trees
• The modal mu-calculus alternation hierarchy is strict
• Fixed point characterization of infinite behavior of finite-state systems
• Deciding Equivalence of Finite Tree Automata
• Theμ-calculus alternation-depth hierarchy is strict on binary trees
• Fixpoint alternation: arithmetic, transition systems, and the binary tree
• Computing the Rabin Index of a Parity Automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Rudiments of \(\mu\)-calculus

This page was built for publication: Deciding low levels of tree-automata hierarchy