Hierarchies of weak automata and weak monadic formulas

DOI10.1016/0304-3975(91)90283-8MaRDI QIDQ805253zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Hierarchies of weakly monotone restarting automata
• scientific article; zbMATH DE number 4051591
• Weak equivalence of higher-dimensional automata
• Weak morphisms of higher dimensional automata
• Alternating automata, the weak monadic theory of trees and its complexity
• Publication:4726235
• scientific article; zbMATH DE number 1670757
• scientific article; zbMATH DE number 3874623
• Weighted automata and monadic second order logic

Cites work

• scientific article; zbMATH DE number 3990873 (Why is no real title available?)
• scientific article; zbMATH DE number 4051591 (Why is no real title available?)
• scientific article; zbMATH DE number 3790415 (Why is no real title available?)
• scientific article; zbMATH DE number 3999901 (Why is no real title available?)
• scientific article; zbMATH DE number 3339435 (Why is no real title available?)
• scientific article; zbMATH DE number 3358465 (Why is no real title available?)
• Alternating automata on infinite trees
• Generalized finite automata theory with an application to a decision problem of second-order logic
• The monadic second order theory of all countable ordinals

Cited in

(22)

• Computing the Rabin Index of a Parity Automaton
• On the weak index problem for game automata
• scientific article; zbMATH DE number 1670757 (Why is no real title available?)
• scientific article; zbMATH DE number 4051591 (Why is no real title available?)
• Deciding low levels of tree-automata hierarchy
• Complexity of weak acceptance conditions in tree automata.
• Definable operations on weakly recognizable sets of trees
• scientific article; zbMATH DE number 3999901 (Why is no real title available?)
• Alternating automata with start formulas
• Theμ-calculus alternation-depth hierarchy is strict on binary trees
• Weak index versus Borel rank
• Weak equivalence of higher-dimensional automata
• Axiomatising extended computation tree logic
• Verification, Model Checking, and Abstract Interpretation
• On the Way to Alternating Weak Automata
• Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
• Weak morphisms of higher dimensional automata
• Permissive strategies: from parity games to safety games
• scientific article; zbMATH DE number 4051592 (Why is no real title available?)
• A gap property of deterministic tree languages.
• Index problems for game automata
• On the separation question for tree languages

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

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