DROPS

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.ISAAC.2022.4

Algorithms for Coloring Reconfiguration Under Recolorability Digraphs

Authors: Soichiro Fujii, Yuni Iwamasa, Kei Kimura, and Akira Suzuki

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract

In the k-Recoloring problem, we are given two (vertex-)colorings of a graph using k colors, and asked to transform one into the other by recoloring only one vertex at a time, while at all times maintaining a proper k-coloring. This problem is known to be solvable in polynomial time if k ≤ 3, and is PSPACE-complete if k ≥ 4. In this paper, we consider a (directed) recolorability constraint on the k colors, which forbids some pairs of colors to be recolored directly. The recolorability constraint is given in terms of a digraph R, whose vertices correspond to the colors and whose arcs represent the pairs of colors that can be recolored directly. We provide algorithms for the problem based on the structure of recolorability constraints R, showing that the problem is solvable in linear time when R is a directed cycle or is in a class of multitrees.

Cite as

Soichiro Fujii, Yuni Iwamasa, Kei Kimura, and Akira Suzuki. Algorithms for Coloring Reconfiguration Under Recolorability Digraphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fujii_et_al:LIPIcs.ISAAC.2022.4,
  author =	{Fujii, Soichiro and Iwamasa, Yuni and Kimura, Kei and Suzuki, Akira},
  title =	{{Algorithms for Coloring Reconfiguration Under Recolorability Digraphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.4},
  URN =		{urn:nbn:de:0030-drops-172896},
  doi =		{10.4230/LIPIcs.ISAAC.2022.4},
  annote =	{Keywords: combinatorial reconfiguration, graph coloring, recolorability, recoloring}
}

Search Results

Documents authored by Fujii, Soichiro

Monads and Distributive Laws in Substructural Contexts

Abstract

Cite as

Algorithms for Coloring Reconfiguration Under Recolorability Digraphs

Abstract

Cite as

Thanks for your feedback!

Could not send message