The Theory of Universal Graphs for Infinite Duration Games

DOI10.46298/lmcs-18(3:29)2022OpenAlexW3154344524MaRDI QIDQ5043588

Paweł Gawrychowski, Nathanaël Fijalkow, Pierre Ohlmann, Thomas Colcombet

Publication date: 6 October 2022

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2104.05262

zbMATH Keywords

parity gamesuniversal graphsgames on graphsmean payoff games

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Related Items (2)

The Theory of Universal Graphs for Infinite Duration Games ⋮ Playing Safe, Ten Years Later

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Faster algorithms for mean-payoff games
• An application of simultaneous diophantine approximation in combinatorial optimization
• Positional strategies for mean payoff games
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite games played on finite graphs
• The complexity of mean payoff games on graphs
• Linear programming, the simplex algorithm and simple polytopes
• A subexponential bound for linear programming
• Universal graphs and good for games automata: new tools for infinite duration games
• The complexity of multi-mean-payoff and multi-energy games
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Half-Positional Determinacy of Infinite Games
• Clique-Width and Parity Games
• Solving Games Without Determinization
• The Theory of Stabilisation Monoids and Regular Cost Functions
• The Bridge Between Regular Cost Functions and Omega-Regular Languages
• Deciding parity games in quasipolynomial time
• The Theory of Universal Graphs for Infinite Duration Games
• Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• A pseudo-quasi-polynomial algorithm for mean-payoff parity games
• A modal μ perspective on solving parity games in quasi-polynomial time
• Quasipolynomial Set-Based Symbolic Algorithms for Parity Games
• Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
• Parity and Streett Games with Costs
• Formal Methods for Components and Objects
• Computer Aided Verification

This page was built for publication: The Theory of Universal Graphs for Infinite Duration Games