2026-08-15T09:08:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23573 2025-10-27T10:40:14Z ddc:004 open_access

Pareto Fronts for Compositionally Solving String Diagrams of Parity Games Watanabe, Kazuki parity game compositionality string diagram 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kazuki Watanabe 2025 Is Part Of LIPIcs, Volume 342, 11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CALCO.2025.14 urn:nbn:de:0030-drops-235734 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2025.14 eng https://creativecommons.org/licenses/by/4.0/legalcode