Faster Game Solving by Fixpoint Acceleration
<|reference_start|>Faster Game Solving by Fixpoint Acceleration: 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-appearence-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.<|reference_end|>
@article{hausmann2024faster,
    title={Faster Game Solving by Fixpoint Acceleration},
    author={Daniel Hausmann},
    journal={arXiv preprint arXiv:2404.13687},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.13687},
    primaryClass={cs.GT cs.LO}
}