3 Search Results for "Master, Jade"

Document
DOI: 10.4230/LIPIcs.CALCO.2025.14
Pareto Fronts for Compositionally Solving String Diagrams of Parity Games

Authors: Kazuki Watanabe

Published in: LIPIcs, Volume 342, 11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025)

Abstract
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.
Cite as

Kazuki Watanabe. Pareto Fronts for Compositionally Solving String Diagrams of Parity Games. In 11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 342, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{watanabe:LIPIcs.CALCO.2025.14,
  author =	{Watanabe, Kazuki},
  title =	{{Pareto Fronts for Compositionally Solving String Diagrams of Parity Games}},
  booktitle =	{11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-383-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{342},
  editor =	{C\^{i}rstea, Corina and Knapp, Alexander},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2025.14},
  URN =		{urn:nbn:de:0030-drops-235734},
  doi =		{10.4230/LIPIcs.CALCO.2025.14},
  annote =	{Keywords: parity game, compositionality, string diagram}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2021.20
The Open Algebraic Path Problem

Authors: Jade Master

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
The algebraic path problem provides a general setting for shortest path algorithms in optimization and computer science. We explain the universal property of solutions to the algebraic path problem by constructing a left adjoint functor whose values are given by these solutions. This paper extends the algebraic path problem to networks equipped with input and output boundaries. We show that the algebraic path problem is functorial as a mapping from a double category whose horizontal composition is gluing of open networks. We introduce functional open matrices, for which the functoriality of the algebraic path problem has a more practical expression.
Cite as

Jade Master. The Open Algebraic Path Problem. In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{master:LIPIcs.CALCO.2021.20,
  author =	{Master, Jade},
  title =	{{The Open Algebraic Path Problem}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.20},
  URN =		{urn:nbn:de:0030-drops-153754},
  doi =		{10.4230/LIPIcs.CALCO.2021.20},
  annote =	{Keywords: The Algebraic Path Problem, Open Systems, Shortest Paths, Categorical Semantics, Compositionality}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.17
Graph Traversals as Universal Constructions

Authors: Siddharth Bhaskar and Robin Kaarsgaard

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We exploit a decomposition of graph traversals to give a novel characterization of depth-first and breadth-first traversals by means of universal constructions. Specifically, we introduce functors from two different categories of edge-ordered directed graphs into two different categories of transitively closed edge-ordered graphs; one defines the lexicographic depth-first traversal and the other the lexicographic breadth-first traversal. We show that each functor factors as a composition of universal constructions, and that the usual presentation of traversals as linear orders on vertices can be recovered with the addition of an inclusion functor. Finally, we raise the question of to what extent we can recover search algorithms from the categorical description of the traversal they compute.
Cite as

Siddharth Bhaskar and Robin Kaarsgaard. Graph Traversals as Universal Constructions. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.MFCS.2021.17,
  author =	{Bhaskar, Siddharth and Kaarsgaard, Robin},
  title =	{{Graph Traversals as Universal Constructions}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.17},
  URN =		{urn:nbn:de:0030-drops-144573},
  doi =		{10.4230/LIPIcs.MFCS.2021.17},
  annote =	{Keywords: graph traversals, adjunctions, universal constructions, category theory}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 2 2021

  • Refine by Author
  • 1 Bhaskar, Siddharth
  • 1 Kaarsgaard, Robin
  • 1 Master, Jade
  • 1 Watanabe, Kazuki

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Theory of computation → Categorical semantics
  • 1 Theory of computation → Models of computation
  • 1 Theory of computation → Operational semantics
  • 1 Theory of computation → Verification by model checking

  • Refine by Keyword
  • 1 Categorical Semantics
  • 1 Compositionality
  • 1 Open Systems
  • 1 Shortest Paths
  • 1 The Algebraic Path Problem
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact