Infinite games played on finite graphs

DOI10.1016/0168-0072(93)90036-DzbMath0798.90151OpenAlexW1971138850MaRDI QIDQ1314640

Publication date: 7 March 1994

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(93)90036-d

zbMATH Keywords

algorithm complexity analysis games of perfect information concurrent computations infinite game played on a finite graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Games involving graphs (91A43) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (79)

On the positional determinacy of edge-labeled games ⋮ μ-Bicomplete Categories and Parity Games ⋮ Consistent Consequence for Boolean Equation Systems ⋮ The Theory of Universal Graphs for Infinite Duration Games ⋮ Modular strategies for recursive game graphs ⋮ Memoryless determinacy of parity and mean payoff games: a simple proof ⋮ Quantitative solution of omega-regular games ⋮ Symmetric Strategy Improvement ⋮ The mu-calculus and Model Checking ⋮ Graph Games and Reactive Synthesis ⋮ PLAYING MULLER GAMES IN A HURRY ⋮ Synthesis for Structure Rewriting Systems ⋮ From Parity and Payoff Games to Linear Programming ⋮ Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition ⋮ Infinite games on finite graphs using grossone ⋮ Solving parity games in big steps ⋮ Parity game reductions ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ McNaughton games and extracting strategies for concurrent programs ⋮ Unnamed Item ⋮ Update games and update networks ⋮ Deciding the unguarded modal -calculus ⋮ Alternating traps in Muller and parity games ⋮ Finite-state strategies in delay games ⋮ Robust worst cases for parity games algorithms ⋮ Parameterized Algorithms for Parity Games ⋮ Fixed point characterization of infinite behavior of finite-state systems ⋮ Information tracking in games on graphs ⋮ Finite automata on timed $\omega$-trees ⋮ Taming strategy logic: non-recurrent fragments ⋮ An impossibility result in automata-theoretic reinforcement learning ⋮ Reachability games and parity games ⋮ Universal algorithms for parity games and nested fixpoints ⋮ Randomness for free ⋮ A survey of stochastic $\omega $-regular games ⋮ Continuous Positional Payoffs ⋮ Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games ⋮ Graph operations on parity games and polynomial-time algorithms ⋮ Unnamed Item ⋮ Infinite Games on Finite Graphs Using Grossone ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Strategy construction for parity games with imperfect information ⋮ FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES ⋮ Unnamed Item ⋮ Strategy Construction for Parity Games with Imperfect Information ⋮ Exploring the boundary of half-positionality ⋮ Down the Borel hierarchy: solving Muller games via safety games ⋮ Indecision and delays are the parents of failure -- taming them algorithmically by synthesizing delay-resilient control ⋮ Deductive verification of alternating systems ⋮ Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra ⋮ Solving parity games via priority promotion ⋮ The Modal μ-Calculus Caught Off Guard ⋮ A selection property of the boolean $\mu $-calculus and some of its applications ⋮ A survey of partial-observation stochastic parity games ⋮ New deterministic algorithms for solving parity games ⋮ Selfish cops and passive robber: qualitative games ⋮ Energy parity games ⋮ Feasibility analysis of sporadic real-time multiprocessor task systems ⋮ Unnamed Item ⋮ Free $\mu$-lattices ⋮ Church’s Problem and a Tour through Automata Theory ⋮ Solving μ-Calculus Parity Games by Symbolic Planning ⋮ Solving Parity Games in Big Steps ⋮ Improving parity games in practice ⋮ Note on winning positions on pushdown games with $\omega$-regular conditions ⋮ Decoy allocation games on graphs with temporal logic objectives ⋮ Extracting Winning Strategies in Update Games ⋮ Büchi Good-for-Games Automata Are Efficiently Recognizable ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time ⋮ Infinite games on finitely coloured graphs with applications to automata on infinite trees ⋮ Quantitatively fair scheduling ⋮ Structural measures for games and process control in the branch learning model ⋮ Minimal separating sets for acceptance conditions in Muller automata ⋮ Unnamed Item ⋮ Learning to win process-control games watching game-masters ⋮ Monadic second-order logic on tree-like structures

Cites Work

This page was built for publication: Infinite games played on finite graphs