Thomas Colcombet ; Nathanaël Fijalkow ; Paweł Gawrychowski ; Pierre Ohlmann - The Theory of Universal Graphs for Infinite Duration Games

lmcs:7715 - Logical Methods in Computer Science, September 7, 2022, Volume 18, Issue 3 - https://doi.org/10.46298/lmcs-18(3:29)2022
The Theory of Universal Graphs for Infinite Duration Games

Authors: Thomas Colcombet ; Nathanaël Fijalkow ; Paweł Gawrychowski ; Pierre Ohlmann

    We introduce the notion of universal graphs as a tool for constructing algorithms solving games of infinite duration such as parity games and mean payoff games. In the first part we develop the theory of universal graphs, with two goals: showing an equivalence and normalisation result between different recently introduced related models, and constructing generic value iteration algorithms for any positionally determined objective. In the second part we give four applications: to parity games, to mean payoff games, to a disjunction between a parity and a mean payoff objective, and to disjunctions of several mean payoff objectives. For each of these four cases we construct algorithms achieving or improving over the best known time and space complexity.


    Volume: Volume 18, Issue 3
    Published on: September 7, 2022
    Accepted on: August 30, 2022
    Submitted on: July 28, 2021
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Computer Science and Game Theory

    Share

    Consultation statistics

    This page has been seen 458 times.
    This article's PDF has been downloaded 214 times.