DROPS

Document

Invited Talk

DOI: 10.4230/LIPIcs.CONCUR.2026.5

A Coalgebraic Dijkstra Algorithm (Invited Talk)

Authors: Takahiro Sanada, Yoàv Montacute, Kittiphon Phalakarn, and Ichiro Hasuo

Published in: LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026)

Abstract

The Dijkstra algorithm is a classical method for solving the shortest path problem on weighted graphs. There are several variations of the Dijkstra algorithm, including algorithms for the widest path problem and for two-player games. In this paper, we introduce the coalgebraic shortest path problem (CSPP), a unifying framework for a broad class of optimization problems on state-transition systems. This framework encompasses not only the aforementioned problems but also new ones such as the shortest binary tree problem. We further present a coalgebraic Dijkstra algorithm for solving the CSPP efficiently under a suitable condition. Our condition is necessary and sufficient for the algorithm to return correct solutions, thereby providing a precise criterion for when Dijkstra-style acceleration is possible. We also show that the proposed algorithm achieves asymptotic complexity comparable to that of the classical Dijkstra algorithm.

Cite as

Takahiro Sanada, Yoàv Montacute, Kittiphon Phalakarn, and Ichiro Hasuo. A Coalgebraic Dijkstra Algorithm (Invited Talk). In 37th International Conference on Concurrency Theory (CONCUR 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 391, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{sanada_et_al:LIPIcs.CONCUR.2026.5,
  author =	{Sanada, Takahiro and Montacute, Yo\`{a}v and Phalakarn, Kittiphon and Hasuo, Ichiro},
  title =	{{A Coalgebraic Dijkstra Algorithm}},
  booktitle =	{37th International Conference on Concurrency Theory (CONCUR 2026)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-447-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{391},
  editor =	{Sokolova, Ana and Totzke, Patrick},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.5},
  URN =		{urn:nbn:de:0030-drops-273365},
  doi =		{10.4230/LIPIcs.CONCUR.2026.5},
  annote =	{Keywords: Coalgebra, Greatest fixed point, Dijkstra’s algorithm, Shortest path}
}

Document

Early Ideas

DOI: 10.4230/LIPIcs.CALCO.2021.21

Preorder-Constrained Simulation for Nondeterministic Automata (Early Ideas)

Authors: Koko Muroya, Takahiro Sanada, and Natsuki Urabe

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

Abstract

We describe our ongoing work on generalizing some quantitatively constrained notions of weak simulation up-to that are recently introduced for deterministic systems modeling program execution. We present and discuss a new notion dubbed preorder-constrained simulation that allows comparison between words using a preorder, instead of equality.

Cite as

Koko Muroya, Takahiro Sanada, and Natsuki Urabe. Preorder-Constrained Simulation for Nondeterministic Automata (Early Ideas). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 21:1-21:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{muroya_et_al:LIPIcs.CALCO.2021.21,
  author =	{Muroya, Koko and Sanada, Takahiro and Urabe, Natsuki},
  title =	{{Preorder-Constrained Simulation for Nondeterministic Automata}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{21:1--21:5},
  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.21},
  URN =		{urn:nbn:de:0030-drops-153762},
  doi =		{10.4230/LIPIcs.CALCO.2021.21},
  annote =	{Keywords: simulation, weak simulation, up-to technique, language inclusion, preorder}
}

Search Results

Documents authored by Sanada, Takahiro

A Coalgebraic Dijkstra Algorithm (Invited Talk)

Abstract

Cite as

Preorder-Constrained Simulation for Nondeterministic Automata (Early Ideas)

Abstract

Cite as

Thanks for your feedback!

Could not send message