Pareto Fronts for Compositionally Solving String Diagrams of Parity Games
<|reference_start|>Pareto Fronts for Compositionally Solving String Diagrams of Parity Games: Open parity games are proposed as a compositional extension of parity games with algebraic operations, forming string diagrams of parity games. A potential application of string diagrams of parity games is to describe a large parity game with a given compositional structure and solve it efficiently as a divide-and-conquer algorithm by exploiting its compositional structure. Building on our recent progress in open Markov decision processes, we introduce Pareto fronts of open parity games, offering a framework for multi-objective solutions. We establish the positional determinacy of open parity games with respect to their Pareto fronts through a novel translation method. Our translation converts an open parity game into a parity game tailored to a given single-objective. Furthermore, we present a simple algorithm for solving open parity games, derived from this translation that allows the application of existing efficient algorithms for parity games. Expanding on this foundation, we develop a compositional algorithm for string diagrams of parity games.<|reference_end|>
@article{watanabe2024pareto,
    title={Pareto Fronts for Compositionally Solving String Diagrams of Parity
  Games},
    author={Kazuki Watanabe},
    journal={arXiv preprint arXiv:2406.17240},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.17240},
    primaryClass={cs.LO}
}