On the Way to Alternating Weak Automata

DOI10.4230/LIPIcs.FSTTCS.2018.21OpenAlexW2907557140MaRDI QIDQ5090957

Karoliina Lehtinen, Udi Boker

Publication date: 21 July 2022

Full work available at URL: https://dblp.uni-trier.de/db/conf/fsttcs/fsttcs2018.html#BokerL18

zbMATH Keywords

parity gamesalternating automataparity automataweak automata

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Related Items (3)

Improved complexity analysis of quasi-polynomial algorithms solving parity games ⋮ Unnamed Item ⋮ Quasipolynomial computation of nested fixpoints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• Hierarchies of weak automata and weak monadic formulas
• On alternating \(\omega\)-automata
• The modal mu-calculus alternation hierarchy is strict
• A gap property of deterministic tree languages.
• \(\varSigma^{\mu}_2\) is decidable for \(\varPi^{\mu}_2\)
• Solving Parity Games Using an Automata-Based Algorithm
• Translating to Co-Büchi Made Tight, Unified, and Useful
• Weak alternating automata are not that weak
• Alternating Tree Automata and Parity Games
• Deciding the topological complexity of Büchi languages *
• Deciding parity games in quasipolynomial time
• Automaton-Based Criteria for Membership in CTL
• A modal μ perspective on solving parity games in quasi-polynomial time
• Testing and generating infinite sequences by a finite automaton

This page was built for publication: On the Way to Alternating Weak Automata