Explicit Muller Games are PTIME

DOI10.4230/LIPIcs.FSTTCS.2008.1756zbMath1248.68331OpenAlexW2240543079MaRDI QIDQ3165962

Florian Horn

Publication date: 19 October 2012

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

zbMATH Keywords

model checkinggamesMuller gamesgame complexityauthomata

Mathematics Subject Classification ID

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

Related Items (6)

Stochastic Games with Finitary Objectives ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Alternating traps in Muller and parity games ⋮ Unnamed Item ⋮ Down the Borel hierarchy: solving Muller games via safety games ⋮ Constrained existence problem for weak subgame perfect equilibria with \(\omega \)-regular Boolean objectives

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