DROPS

Document

DOI: 10.4230/LIPIcs.LICS.2026.54

A Categorical Perspective on Constraint Satisfaction: The Wonderland of Adjunctions

Authors: Maximilian Hadek, Tomáš Jakl, and Jakub Opršal

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

Abstract

The so-called algebraic approach to the constraint satisfaction problem (CSP) has been a prevalent method of the study of complexity of these problems since early 2000’s. The core of this approach is the notion of polymorphisms which determine the complexity of the problem (up to log-space reductions). In the past few years, a new, more general version of the CSP emerged, the promise constraint satisfaction problem (PCSP), and the notion of polymorphisms and most of the core theses of the algebraic approach were generalised to the promise setting. Nevertheless, recent work also suggests that insights from other fields are immensely useful in the study of PCSPs including algebraic topology. In this paper, we provide an entry point for category-theorists into the study of complexity of CSPs and PCSPs. We show that many standard CSP notions have clear and well-known categorical counterparts. For example, the algebraic structure of polymorphisms can be described as a set-functor defined as a right Kan extension. We provide purely categorical proofs of core results of the algebraic approach including a proof that the complexity only depends on the polymorphisms. Our new proofs are substantially shorter and, from the categorical perspective, cleaner than previous proofs of the same results. Moreover, as expected, they are applicable more widely. We believe that, in particular in the case of PCSPs, category theory brings insights that can help solve some of the current challenges of the field.

Cite as

Maximilian Hadek, Tomáš Jakl, and Jakub Opršal. A Categorical Perspective on Constraint Satisfaction: The Wonderland of Adjunctions. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 54:1-54:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hadek_et_al:LIPIcs.LICS.2026.54,
  author =	{Hadek, Maximilian and Jakl, Tom\'{a}\v{s} and Opr\v{s}al, Jakub},
  title =	{{A Categorical Perspective on Constraint Satisfaction: The Wonderland of Adjunctions}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{54:1--54:27},
  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.54},
  URN =		{urn:nbn:de:0030-drops-268415},
  doi =		{10.4230/LIPIcs.LICS.2026.54},
  annote =	{Keywords: constraint satisfaction problem, categorical models and logics}
}

Document

DOI: 10.4230/LIPIcs.CALCO.2017.14

Free Constructions and Coproducts of d-Frames

Authors: Tomás Jakl and Achim Jung

Published in: LIPIcs, Volume 72, 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)

Abstract

A general theory of presentations for d-frames does not yet exist. We review the difficulties and give sufficient conditions for when they can be overcome. As an application we prove that the category of d-frames is closed under coproducts.

Cite as

Tomás Jakl and Achim Jung. Free Constructions and Coproducts of d-Frames. In 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 72, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jakl_et_al:LIPIcs.CALCO.2017.14,
  author =	{Jakl, Tom\'{a}s and Jung, Achim},
  title =	{{Free Constructions and Coproducts of d-Frames}},
  booktitle =	{7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-033-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{72},
  editor =	{Bonchi, Filippo and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2017.14},
  URN =		{urn:nbn:de:0030-drops-80304},
  doi =		{10.4230/LIPIcs.CALCO.2017.14},
  annote =	{Keywords: Free construction, d-frame, coproduct, C-ideals}
}

Search Results

Documents authored by Jakl, Tomás

A Categorical Perspective on Constraint Satisfaction: The Wonderland of Adjunctions

Abstract

Cite as

Free Constructions and Coproducts of d-Frames

Abstract

Cite as

Thanks for your feedback!

Could not send message