Explicit Muller games are PTIME

DOI10.4230/LIPICS.FSTTCS.2008.1756MaRDI QIDQ3165962zbMATH OpenOpenAlexFDO

Authors Florian Horn

Publication date 19 October 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_1c41.html

zbMATH Keywords

authomatagame complexitygamesmodel checkingMuller games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) 2-person games (91A05) Games involving graphs (91A43) Applications of game theory (91A80)

Recommendations

• Mathematical Foundations of Computer Science 2005
• scientific article; zbMATH DE number 2077117
• Finitary winning in \({\omega}\)-regular games
• The complexity of stochastic Müller games
• Stochastic Müller Games are PSPACE-Complete

Cited in

(14)

• Constrained existence problem for weak subgame perfect equilibria with \(\omega \)-regular Boolean objectives
• Stochastic Games with Finitary Objectives
• Alternating traps in Muller and parity games
• scientific article; zbMATH DE number 2077117 (Why is no real title available?)
• Down the Borel hierarchy: solving Muller games via safety games
• Parameterized complexity of games with monotonically ordered \(\omega\)-regular objectives
• Deciding Parity Games in Quasi-polynomial Time
• Mathematical Foundations of Computer Science 2005
• Stackelberg-Pareto synthesis
• From Muller to parity and Rabin qutomata: optimal transformations preserving (history) determinism
• Linear-time safe-alternating DFS and SCCs
• Optimal transformations of games and automata using Muller conditions
• Exponential time algorithms for deciding regular games
• Deciding regular games: a playground for exponential time algorithms

This page was built for publication: Explicit Muller games are PTIME

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