On the Way to Alternating Weak Automata

DOI10.4230/LIPICS.FSTTCS.2018.21MaRDI QIDQ5090957zbMATH OpenOpenAlexFDO

Authors Udi Boker, Karoliina Lehtinen

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)

Recommendations

• Alternating weak automata from universal trees
• scientific article; zbMATH DE number 1775458
• Weak alternating automata are not that weak
• Unambiguous Büchi Is Weak
• On the strength of unambiguous tree automata

Cites work

• scientific article; zbMATH DE number 1136070 (Why is no real title available?)
• scientific article; zbMATH DE number 1500644 (Why is no real title available?)
• scientific article; zbMATH DE number 1775458 (Why is no real title available?)
• A gap property of deterministic tree languages.
• A modal \(\mu\) perspective on solving parity games in quasi-polynomial time
• Alternating Tree Automata and Parity Games
• Automaton-Based Criteria for Membership in CTL
• Deciding parity games in quasipolynomial time
• Deciding the topological complexity of Büchi languages
• Deciding the weak definability of Büchi definable tree languages
• Hierarchies of weak automata and weak monadic formulas
• On alternating \(\omega\)-automata
• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• Solving parity games using an automata-based algorithm
• Succinct progress measures for solving parity games
• Testing and generating infinite sequences by a finite automaton
• The modal mu-calculus alternation hierarchy is strict
• Translating to co-Büchi made tight, unified, and useful
• Weak alternating automata are not that weak
• \(\varSigma^{\mu}_2\) is decidable for \(\varPi^{\mu}_2\)

Cited in

(14)

• A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata
• Quasi-weak cost automata: a new variant of weakness
• Improved complexity analysis of quasi-polynomial algorithms solving parity games
• Verification, Model Checking, and Abstract Interpretation
• Weak alternating timed automata
• Mathematical Foundations of Computer Science 2003
• Alternating Weighted Automata
• Quasipolynomial computation of nested fixpoints
• scientific article; zbMATH DE number 7649926 (Why is no real title available?)
• Weak equivalence of higher-dimensional automata
• scientific article; zbMATH DE number 1670757 (Why is no real title available?)
• scientific article; zbMATH DE number 5585001 (Why is no real title available?)
• On the power of alternation in automata theory
• On input read-modes of alternating Turing machines

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

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