The complexity of partial-observation parity games

DOI10.1007/978-3-642-16242-8_1MaRDI QIDQ4933292zbMATH OpenOpenAlexFDO

Authors Krishnendu Chatterjee, Laurent Doyen

Publication date 12 October 2010

Published in Logic for Programming, Artificial Intelligence, and Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16242-8_1

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Games involving graphs (91A43)

Recommendations

• A survey of partial-observation stochastic parity games
• The complexity of partial-observation stochastic parity games with finite-memory strategies
• Parity games with partial information played on graphs of bounded complexity
• Partial-observation stochastic reachability and parity games
• Games with a Weak Adversary

Cited in

(19)

• Looking at mean payoff through foggy windows
• A survey of partial-observation stochastic parity games
• Compositional construction of most general controllers
• Mean-payoff games with partial observation
• Relating paths in transition systems: the fall of the modal mu-calculus
• Graph Games and Reactive Synthesis
• The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete
• Mean-payoff games with partial-observation (extended abstract)
• Randomness for free
• Asynchronous -regular games with partial information
• Parity games with partial information played on graphs of bounded complexity
• Obligation Blackwell games and p-automata
• Partial-observation stochastic games, how to win when belief fails
• Perspective games
• A game-theoretic approach to indistinguishability of winning objectives as user privacy
• Perspective games with notifications
• Model-checking strategic abilities in information-sharing systems
• The non-cooperative rational synthesis problem for SPEs and -regular objectives
• The Rabin index of parity games: its complexity and approximation

This page was built for publication: The complexity of partial-observation parity games

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