Büchi Good-for-Games Automata Are Efficiently Recognizable

DOI10.4230/LIPIcs.FSTTCS.2018.16OpenAlexW2901103347MaRDI QIDQ5090951

Marc Bagnol, Denis Kuperberg

Publication date: 21 July 2022

Full work available at URL: https://hal.archives-ouvertes.fr/hal-01910632

zbMATH Keywords

automatapolynomial timenondeterminismgamesBüchi

Mathematics Subject Classification ID

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

Related Items

Unnamed Item, On history-deterministic one-counter nets, A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct, History-deterministic timed automata are not determinizable, Token Games and History-Deterministic Quantitative-Automata, Unnamed Item, Unnamed Item, Unnamed Item, Minimizing GFG Transition-Based Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Solving parity games in big steps
• Infinite games played on finite graphs
• Progress measures, immediate determinacy, and a subset construction for tree automata
• Forms of Determinism for Automata (Invited Talk)
• Width of Non-deterministic Automata
• On Determinisation of Good-for-Games Automata
• Solving Games Without Determinization
• The Theory of Stabilisation Monoids and Regular Cost Functions
• Deciding parity games in quasipolynomial time
• How Deterministic are Good-For-Games Automata?
• Nondeterminism in the Presence of a Diverse or Unknown Future
• Are Good-for-Games Automata Good for Probabilistic Model Checking?
• Solving Sequential Conditions by Finite-State Strategies