2024/04/21 by Daniel Hausmann, Hausmann, Daniel
Computer Science · #Artificial Intelligence in Games #Computer Science and Game Theory (cs.GT) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Metaheuristic Optimization Algorithms Research
paper · pdf · doi:10.48550/arxiv.2404.13687
openalex publication_date 2024/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a method for solving parity games with acyclic (DAG) sub-structures by computing nested fixpoints of a DAG attractor function that lives over the non-DAG parts of the game, thereby restricting the domain of the involved fixpoint operators. Intuitively, this corresponds to accelerating fixpoint computation by inlining cycle-free parts during the solution of parity games, leading to earlier convergence. We also present an economic later-appearance-record construction that takes Emerson-Lei games to parity games, and show that it preserves DAG sub-structures; it follows that the proposed method can be used also for the accelerated solution of Emerson-Lei games.