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

DOI: 10.4230/LIPIcs.LICS.2026.45

Monads and Distributive Laws in Substructural Contexts

Authors: Soichiro Fujii, Yun Chen Tsai, Yoàv Montacute, and Ichiro Hasuo

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract

We present a categorical theory of monads and distributive laws in substructural contexts. In the study of distributive laws, the roles of (the absence of) structural rules for variable contexts have been recognized; our theory formalizes these substructural situations using Tronin’s verbal categories W, in a uniform and presentation-independent manner. We introduce the classes of W-operadic monads (those defined via the structural rules in W) and of W-commutative monads (those invariant under the structural rules in W). We give a canonical construction of a distributive law ST → TS of monads on Set; it is applicable when S is W-operadic and T is W-commutative (under mild conditions). This accounts for many known and new distributive laws. Even when S fails to be W-operadic, we can refine S and force W-operadicity; this captures Varacca and Winskel’s construction of indexed valuations.

Cite as

Soichiro Fujii, Yun Chen Tsai, Yoàv Montacute, and Ichiro Hasuo. Monads and Distributive Laws in Substructural Contexts. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 45:1-45:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fujii_et_al:LIPIcs.LICS.2026.45,
  author =	{Fujii, Soichiro and Tsai, Yun Chen and Montacute, Yo\`{a}v and Hasuo, Ichiro},
  title =	{{Monads and Distributive Laws in Substructural Contexts}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{45:1--45:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.45},
  URN =		{urn:nbn:de:0030-drops-268324},
  doi =		{10.4230/LIPIcs.LICS.2026.45},
  annote =	{Keywords: Monad, distributive law, operad, category theory, effect}
}

Document

DOI: 10.4230/LIPIcs.CSL.2022.19

Dynamic Cantor Derivative Logic

Authors: David Fernández-Duque and Yoàv Montacute

Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)

Abstract

Topological semantics for modal logic based on the Cantor derivative operator gives rise to derivative logics, also referred to as d-logics. Unlike logics based on the topological closure operator, d-logics have not previously been studied in the framework of dynamical systems, which are pairs (X,f) consisting of a topological space X equipped with a continuous function f: X → X. We introduce the logics wK4C, K4C and GLC and show that they all have the finite Kripke model property and are sound and complete with respect to the d-semantics in this dynamical setting. In particular, we prove that wK4C is the d-logic of all dynamic topological systems, K4C is the d-logic of all T_D dynamic topological systems, and GLC is the d-logic of all dynamic topological systems based on a scattered space. We also prove a general result for the case where f is a homeomorphism, which in particular yields soundness and completeness for the corresponding systems wK4H, K4H and GLH. The main contribution of this work is the foundation of a general proof method for finite model property and completeness of dynamic topological d-logics. Furthermore, our result for GLC constitutes the first step towards a proof of completeness for the trimodal topo-temporal language with respect to a finite axiomatisation - something known to be impossible over the class of all spaces.

Cite as

David Fernández-Duque and Yoàv Montacute. Dynamic Cantor Derivative Logic. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fernandezduque_et_al:LIPIcs.CSL.2022.19,
  author =	{Fern\'{a}ndez-Duque, David and Montacute, Yo\`{a}v},
  title =	{{Dynamic Cantor Derivative Logic}},
  booktitle =	{30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-218-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{216},
  editor =	{Manea, Florin and Simpson, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.19},
  URN =		{urn:nbn:de:0030-drops-157397},
  doi =		{10.4230/LIPIcs.CSL.2022.19},
  annote =	{Keywords: dynamic topological logic, Cantor derivative, temporal logic, modal logic}
}

Search Results

Documents authored by Montacute, Yoàv

A Coalgebraic Dijkstra Algorithm (Invited Talk)

Abstract

Cite as

Monads and Distributive Laws in Substructural Contexts

Abstract

Cite as

Dynamic Cantor Derivative Logic

Abstract

Cite as

Thanks for your feedback!

Could not send message