Rabin-Mostowski index problem: a step beyond deterministic automata

DOI10.1109/LICS.2013.56MaRDI QIDQ5271087zbMATH OpenFDO

Authors Alessandro Facchini, Filip Murlak, Michał Skrzypczak

Publication date 3 July 2017

Published in 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/LICS.2013.56

zbMATH Keywords

alternating automatadecidabilitygame automatanondeterministic automataparity automataRabin-Mostowski index

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Recommendations

• Index problems for game automata
• On the weak index problem for game automata
• Computing the rabin index of a regular language of infinite words
• On the separation question for tree languages
• scientific article; zbMATH DE number 3983141

Cited in

(13)

• \(\varSigma^{\mu}_2\) is decidable for \(\varPi^{\mu}_2\)
• Unambiguous Büchi Is Weak
• On the separation question for tree languages
• On the weak index problem for game automata
• Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
• Deciding low levels of tree-automata hierarchy
• Computing the Rabin Index of a Parity Automaton
• Disjunctive form and the modal alternation hierarchy
• Monoidal-closed categories of tree automata
• Index problems for game automata
• Computing the rabin index of a regular language of infinite words
• Computing measures of weak-mso definable sets of trees
• A dichotomy theorem for ordinal ranks in MSO

This page was built for publication: Rabin-Mostowski index problem: a step beyond deterministic automata

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