License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CALCO.2021.20
URN: urn:nbn:de:0030-drops-153754
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15375/
Go to the corresponding LIPIcs Volume Portal

Master, Jade

The Open Algebraic Path Problem

pdf-format:
LIPIcs-CALCO-2021-20.pdf (0.8 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2021/15375},
  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}
}

Keywords: The Algebraic Path Problem, Open Systems, Shortest Paths, Categorical Semantics, Compositionality
Collection: 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)
Issue Date: 2021
Date of publication: 08.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI