Hierarchies of weak automata and weak monadic formulas

DOI10.1016/0304-3975(91)90283-8zbMath0728.68086OpenAlexW1992595180MaRDI QIDQ805253

A. Włodzimierz Mostowski

Publication date: 1991

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

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90283-8

zbMATH Keywords

alternating finite automataMuller indexRabin index

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (12)

Index Problems for Game Automata ⋮ Permissive strategies: from parity games to safety games ⋮ On the Weak Index Problem for Game Automata ⋮ A gap property of deterministic tree languages. ⋮ Alternating automata with start formulas ⋮ Axiomatising extended computation tree logic ⋮ On the separation question for tree languages ⋮ Theμ-calculus alternation-depth hierarchy is strict on binary trees ⋮ Computing the Rabin Index of a Parity Automaton ⋮ On the Way to Alternating Weak Automata ⋮ Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata ⋮ Complexity of weak acceptance conditions in tree automata.

Cites Work

• Alternating automata on infinite trees
• The monadic second order theory of all countable ordinals
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Hierarchies of weak automata and weak monadic formulas