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

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