Mathematical Foundations of Computer Science 2005

DOI10.1007/11549345MaRDI QIDQ5492884zbMATH OpenOpenAlexFDO

Authors Paul Hunter, Anuj Dawar

Publication date 20 October 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11549345

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Games involving graphs (91A43)

Recommendations

• Explicit Muller games are PTIME
• Stochastic Müller Games are PSPACE-Complete
• Automata, Languages and Programming
• Games with winning conditions of high Borel complexity
• Infinite games played on finite graphs

Cited in

(38)

• Games, complexity classes, and approximation algorithms.
• Complexity and monotonicity results for domination games
• Predictive Complexity for Games with Finite Outcome Spaces
• scientific article; zbMATH DE number 6490905 (Why is no real title available?)
• The complexity of request-response games
• ON THE COMPLEXITY OF COMPUTING VALUES OF RESTRICTED GAMES
• Percolation and the complexity of games
• Extracting winning strategies in update games
• Explicit Muller games are PTIME
• Restricted Power - Computational Complexity Results for Strategic Defense Games
• Decision Problems for Nash Equilibria in Stochastic Games
• Alternating traps in Muller and parity games
• A survey of stochastic -regular games
• The complexity of stochastic Müller games
• scientific article; zbMATH DE number 2024632 (Why is no real title available?)
• On the complexity of branching games with regular conditions
• Minkowski games
• Parameterized complexity of games with monotonically ordered \(\omega\)-regular objectives
• Complexity of Unordered CNF Games
• Deciding Parity Games in Quasi-polynomial Time
• Playing Muller games in a hurry
• Assume-admissible synthesis
• On the complexity of problems on simple games
• On Reachability Games of Ordinal Length
• Stochastic Müller Games are PSPACE-Complete
• Automata, Languages and Programming
• The complexity of recursion theoretic games
• Playing games with boxes and diamonds.
• Zielonka DAG acceptance and regular languages over infinite words
• Symbolic solution of Emerson-Lei games for reactive synthesis
• Checking history-determinism is NP-hard for parity automata
• Decidable (ac)counting with Parikh and Muller: adding Presburger arithmetic to monadic second-order logic over tree-interpretable structures
• Faster and smaller solutions of obliging games
• The complexity of simplifying -automata through the alternating cycle decomposition
• Optimal transformations of games and automata using Muller conditions
• Exponential time algorithms for deciding regular games
• On Müller context-free grammars
• Games with winning conditions of high Borel complexity

This page was built for publication: Mathematical Foundations of Computer Science 2005

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