Infinite games on finitely coloured graphs with applications to automata on infinite trees
From MaRDI portal
Publication:1276252
DOI10.1016/S0304-3975(98)00009-7zbMath0915.68120OpenAlexW2060375000WikidataQ30040294 ScholiaQ30040294MaRDI QIDQ1276252
Publication date: 20 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00009-7
Related Items
Abstraction in Fixpoint Logic ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Zielonka DAG acceptance and regular languages over infinite words ⋮ An impossibility result in automata-theoretic reinforcement learning ⋮ Reachability games and parity games ⋮ Universal algorithms for parity games and nested fixpoints ⋮ Improved complexity analysis of quasi-polynomial algorithms solving parity games ⋮ Dissecting \texttt{ltlsynt} ⋮ Justifications and a reconstruction of parity game solving algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Optimizing Winning Strategies in Regular Infinite Games ⋮ On Reachability Games of Ordinal Length ⋮ Free \(\mu\)-lattices ⋮ The Complexity of Nash Equilibria in Infinite Multiplayer Games ⋮ Stochastic Games with Lossy Channels ⋮ The Complexity of CTL* + Linear Past ⋮ Stochastic Müller Games are PSPACE-Complete ⋮ Solving Parity Games in Big Steps ⋮ Unnamed Item ⋮ Monoidal-closed categories of tree automata ⋮ Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time ⋮ Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Good-for-Game QPTL: An Alternating Hodges Semantics ⋮ On the positional determinacy of edge-labeled games ⋮ The finite graph problem for two-way alternating automata. ⋮ μ-Bicomplete Categories and Parity Games ⋮ Family-Based SPL Model Checking Using Parity Games with Variability ⋮ The Theory of Universal Graphs for Infinite Duration Games ⋮ Memoryless determinacy of parity and mean payoff games: a simple proof ⋮ Symmetric Strategy Improvement ⋮ Permissive strategies: from parity games to safety games ⋮ Minimum Attention Controller Synthesis for Omega-Regular Objectives ⋮ Marking shortest paths on pushdown graphs does not preserve MSO decidability ⋮ Automata Theory and Model Checking ⋮ The mu-calculus and Model Checking ⋮ Graph Games and Reactive Synthesis ⋮ Cooking Your Own Parity Game Preorders Through Matching Plays ⋮ Dicing on the Streett ⋮ PLAYING MULLER GAMES IN A HURRY ⋮ TWO LOCAL STRATEGY ITERATION SCHEMES FOR PARITY GAME SOLVING ⋮ Admissible Strategies in Infinite Games over Graphs ⋮ From Parity and Payoff Games to Linear Programming ⋮ Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition ⋮ Solving parity games in big steps ⋮ Parity game reductions ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Generalized matrix projective synchronization of general colored networks with different-dimensional node dynamics ⋮ Measure properties of regular sets of trees ⋮ On the relation between reactive synthesis and supervisory control of non-terminating processes ⋮ Adaptive synchronization and pinning control of colored networks ⋮ Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems ⋮ Alternating traps in Muller and parity games ⋮ Robust worst cases for parity games algorithms ⋮ Parameterized Algorithms for Parity Games ⋮ Entanglement and the complexity of directed graphs ⋮ Theory and computation of discrete state space decompositions for hybrid systems ⋮ Index appearance record with preorders ⋮ Memory Reduction for Strategies in Infinite Games ⋮ The Rabin index of parity games: its complexity and approximation ⋮ Dynamic hierarchical reactive controller synthesis ⋮ A survey of stochastic \(\omega \)-regular games ⋮ The complexity of stochastic Müller games ⋮ Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games ⋮ Unnamed Item ⋮ Graph operations on parity games and polynomial-time algorithms ⋮ The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata ⋮ Memoryless determinacy of finite parity games: another simple proof ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Memoryless determinacy of infinite parity games: another simple proof ⋮ Unnamed Item ⋮ Automated temporal equilibrium analysis: verification and synthesis of multi-player games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Strategy construction for parity games with imperfect information ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A superpolynomial lower bound for strategy iteration based on snare memorization ⋮ FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Descriptive Complexity of Parity Games ⋮ Strategy Construction for Parity Games with Imperfect Information ⋮ Exploring the boundary of half-positionality ⋮ Down the Borel hierarchy: solving Muller games via safety games ⋮ Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis ⋮ Modal and mixed specifications: key decision problems and their complexities ⋮ Deductive verification of alternating systems ⋮ Solving parity games via priority promotion ⋮ Strategies, model checking and branching-time properties in Maude ⋮ Visibly linear temporal logic ⋮ A selection property of the boolean $\mu $-calculus and some of its applications ⋮ Strategy synthesis for multi-dimensional quantitative objectives ⋮ Model Checking Games ⋮ New deterministic algorithms for solving parity games ⋮ Infinite games with finite knowledge gaps ⋮ Energy parity games ⋮ Symbolic approximate time-optimal control ⋮ A delayed promotion policy for parity games ⋮ Cycle detection in computation tree logic ⋮ Solving μ-Calculus Parity Games by Symbolic Planning ⋮ Improving parity games in practice ⋮ Note on winning positions on pushdown games with \(\omega\)-regular conditions ⋮ Quasipolynomial computation of nested fixpoints ⋮ CEGAR for compositional analysis of qualitative properties in Markov decision processes ⋮ Polynomial-Time Under-Approximation of Winning Regions in Parity Games ⋮ On the Complexity of Branching-Time Logics ⋮ Solving Parity Games Using an Automata-Based Algorithm ⋮ Quantitatively fair scheduling ⋮ Solving Parity Games in Practice ⋮ Automata on infinite trees ⋮ Recursive algorithm for parity games requires exponential time ⋮ Branching-time logics repeatedly referring to states ⋮ The GKK algorithm is the fastest over simple mean-payoff games ⋮ Uniform strategies, rational relations and jumping automata ⋮ Synthesis in presence of dynamic links ⋮ Monadic second-order logic on tree-like structures ⋮ Games with winning conditions of high Borel complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An initial semantics for the \(\mu\)-calculus on trees and Rabin's complementation lemma
- Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
- Extension of Gurevich-Harrington's restricted memory determinacy theorem: A criterion for the winning player and an explicit class of winning strategies
- Alternating automata with start formulas
- Borel determinacy
- Infinite games played on finite graphs
- Progress measures, immediate determinacy, and a subset construction for tree automata
- State-strategies for games in Fσδ ∩ Gδσ
- Unforgettable Forgetful Determinacy
- On the synthesis of strategies in infinite games
- Decidability of Second-Order Theories and Automata on Infinite Trees
