Semantics and compositionality for expressiveness and complexity (ESSLLI 2026 Workshop)

This is the homepage of the ESSLLI 2026 workshop whose aim is to bring together researchers who apply semantic approaches in the study of expressiveness and complexity problems in logic. In particular, the objective is to provide a platform for researchers who apply tools from

• category theory,
• algebra, and
• topology

in the algorithm-oriented fields of theoretical computer science, such as

• automata theory,
• descriptive complexity,
• finite model theory, and
• constraint satisfaction.

Examples include the use of category theory in automata theory, formal language theory, in the study of graph invariants, and dynamic programming algorithms. Similarly relevant are applications of algebra and topology in CSP, or applications of duality theory and topology in finite model theory and quantum isomorphisms.

Dates

• Workshop dates: 10-14 August 2026, in Prague
• Submission: 30 April 2026
• Notification: 15 May 2026
• ESSLLI Registration: early until May 31, late after June 1

Invited Tutorials

• Samson Abramsky (on game comonad)
• Jiří Adámek (on universal coalgebra):
  State-Based Systems as Coalgebras and their Minimization

  Various types of systems such as automata, dynamic systems or labelled transition systems, are represented as coalgebras in a category (where the state object lives) using an endofunctor which expresses the dynamics of the system. The terminal coalgebra represents possible behaviours of states. We discuss various approaches to the construction of the terminal coalgebra. For coalgebras in the category of sets one approach is closely connected to the process of state minimization, generalizing the construction of minimal automata for a given language.

• Jakub Opršal (on the algebraic approach to CSP)

Contributed Talks

• Gabriel Goren-Roig - Arboreal Adjunctions from Shapes
• Tomas Jakl - TBA
• Damiano Mazza:
  A Categorical Approach to Descriptive Complexity

  We present an approach to descriptive complexity based on a combination of categorical logic and commutative algebra. The basic objects of this approach are ultrarings, which simultaneously generalize commutative rings and Boolean lextensive categories. As such, they allow to blend together standard algebraic notions (from commutative algebra) and logical notions (from categorical logic), providing a unifying descriptive framework in which complexity classes over arbitrary rings (as in the Blum, Schub, Smale model) and usual, Boolean complexity classes may be captured in a uniform way.

• Paul-André Melliès:
  Recent advances in tensorial logic and functorial game semantics

  Tensorial logic is a primitive logic of sum, tensor and negation which refines linear logic by relaxing the requirement that linear negation is involutive. The logic is designed in such a way that its formulas [modulo canonical isomorphism] are in a one-to-one correspondence with dialogue games, and that its proofs [modulo cut-elimination] are in a one-to-one correspondence with innocent strategies.
  In this introductory talk, I will explain how to incorporate the exponential modality of linear logic in order to expand the proof-theoretic and functorial approach to game semantics beyond the multiplicative and additive fragment of tensorial logic. Somewhat surprisingly, the extension is based on a tensorial logic with two negations: the standard tensorial negation together with a new exponential and backtracking negation.
  My talk will mainly focus on presenting a recent coherence theorem for tensorial logic, which states that the free dialogue category with two negations (tensorial and exponential) coincides with a specific category of innocent and well-bracketed strategies between dialogue games. I will explain the result and use it to derive a general positionality theorem for innocent and well-bracketed strategies.
  This coherence theorem for dialogue categories with two negations represents a significant development in the research programme on functorial game semantics which began around fifteen years ago, inspired by a tentative connection between game semantics and functorial knot theory.

• Larry Moss - TBA
• Cihan Okay:
  Double categories for adaptive quantum computation

  Quantum computation admits several operational models — circuit, measurement-based, magic-state — each capturing different aspects of computational power. We develop a unified framework for these models and their interrelations using double categories. Double port graphs, a bidirectional generalization of port graphs, serve as the syntactic representation of quantum (horizontal) and classical (vertical) information flows within computational models. Quantum operations providing the semantics are described as adaptive instruments, organized into a one-object double category whose two directions correspond to quantum channels and stochastic maps; conversions between computational models are then expressed as double functors. To analyze computational power, we extend the theory of contextuality — building on the sheaf-theoretic framework of Abramsky et al. — to an adaptive setting through the notion of simplicial instruments, which lift presheaf-valued distributions over measurement scenarios to a double-categorical setting. This yields a quantitative characterization of computational power in terms of contextual fraction, leading to a categorical formulation of the result — originating with Raussendorf — that non-contextual resources can compute only affine Boolean functions. The framework thus offers a new syntactic/semantic perspective on the interplay between adaptivity, contextuality, and computational power in quantum computational models.

• Luca Reggio - Representing arboreal categories
• Nihil Shah:
  Reflections on Game Comonad Engineering: Loosely-Guarded and Pebbling

  A game comonad can be viewed as a keystone locking in the connection between logic, homomorphism counting, decompositions, and model-comparison games. Thus, engineering a comonad using one of these aspects yields a guide for new results and constructions in the other aspect. I illustrate this with the latest example: a game comonad capturing hypertree decompositions, equivalence in bounded conjunct guarded logic, and two-sorted finite-variable hyperedge logic. I also formally explicate the connection between this comonad and the pebbling comonad.
  This is joint work with Elias Percy.

• Masaya Taniguchi:
  Decidability of Derivability under Depth Constraints in CG with B and T

  Categorial grammar is a formal framework in which grammatical structure is described using algebraic operations on types, with well-known connections to logic, algebra, and category theory. In particular, there is a long-standing affinity with categorical methods, going back to Lambek’s own categorical analysis of the Lambek calculus. However, even basic computational questions—such as whether a given expression can be derived—can become highly complex.
  In this talk, I present a general technique for proving decidability of derivability in a variant of Combinatory Categorial Grammar (CGBT). The key idea is that if a derivation exists, then there is also one in which all intermediate types have bounded structural depth, determined solely by the input. This allows us to restrict attention to a finite search space, yielding decidability. I will focus on the core intuition behind this depth-bounding argument and its relevance to expressiveness and complexity. This is joint work with K. Tsukamoto and S. Nakatani (University of Tokyo).

• Henning Urbat:
  Demystifying Codensity Monads via Duality

  Codensity monads provide a universal method to generate complex monads from simple functors. Recently, a wide range of important monads in logic, denotational semantics, and probabilistic computation, such as several incarnations of the ultrafilter monad, the Vietoris monad, and the Giry monad, have been presented as codensity monads, using complex arguments. We propose a unifying categorical approach to codensity presentations of monads, based on the idea of relating the presenting functor to a dense functor via a suitable duality between categories. We prove a general presentation result applying to every such situation and demonstrate that most codensity presentations known in the literature emerge from this strikingly simple duality-based setup, drastically alleviating the complexity of their proofs and in many cases completely reducing them to standard duality results. Additionally, we derive a number of novel codensity presentations using our framework, including the first non-trivial codensity presentations for the filter monads on sets and topological spaces, the lower Vietoris monad on topological spaces, and the expectation monad on sets. This talk is based on joint work with Fabian Lenke, Stefan Milius, and Nico Wittrock, presented at STACS 2026.

• Haitian Wang:
  A Categorical Perspective on Kripke Models and Dynamic Epistemic Logic

  Kripke models are a standard relational semantics for modal logic and intuitionistic logic, and they also provide a natural representation of state-based systems with uncertainty. In this talk we present ongoing work on viewing Kripke models through a categorical lens, and work in the category of Kripke models. We investigate how the categorical properties vary along several dimensions, including unpointed vs. pointed vs. multi-pointed models, restrictions to particular classes of frames/models, and different choices of morphisms (e.g. monotone maps vs. bounded morphisms).
  A main motivation comes from Dynamic Epistemic Logic (DEL), where actions (such as public/private announcements and factual changes) are represented using action models and applied to Kripke models via product update, transforming a Kripke model into a new one after the update. Related work by Kishida (2017) gives a categorical perspective on DEL at the level of frames. We extend the framework to the level of models and analyze the functoriality of product update: with monotone maps as morphisms, action models with arbitrary modal preconditions do not in general induce endofunctors, and this motivates alternative treatments such as restricting preconditions or moving to partial-map/Kleisli-style categories. Finally, we outline how these categorical constructions may provide a new understanding of constructions in DEL such as action emulation, where we seek a categorical notion of equivalence between action models.

Submitting instructions

Apart from invited lectures there will be a number of contributed talks. If you are interested in giving a talk, please write to tomas.jakl@cvut.cz with a title of your talk and a short abstract (1-2 paragraphs).

Although the deadline for submission is 30 April 2026, please feel free to write earlier, to express the intent to submit.

Schedule overview

Moreover, the participants are encouraged to also take part in the rest of the (Week 2) ESSLLI programme.

Local information

Please follow the instructions at the ESSLLI website.

We would only add the following:

• Please book your hotels early. Summer is a busy tourist season and the most affordable hotels run out quickly.
• Public transport is the best way to get around Prague. You can use your contactless card to buy tickets right on the buses and trams. In case you also travel by subway, these have to be purchased before entering the subway. There should be ticket machines at the entrance. Also, you can transfer between different modes of transport on a single ticket, so long as this is within the ticket’s time constraints (30 min, 90 min, 24 hours).
• In case you really need to use taxi, it is recommended to use Uber, Bolt or similar apps as the standard taxi drivers do not have a good reputation when it comes to treating tourists.

Workshop dinner

Workshop dinner takes place on Tuesday, the 11th of August. All speakers of the workshop are invited. The dinner starts at 7pm at the U Pětníka restaurant, which you can find on the address: Lotyšská 645/8, Praha 6.

In case any of the speakers does not plan to attend, please let Tomáš know. Similarly, if you are not one of the speakers but you would like to attend, feel free to contact us and we will see what can be done.

Similar events

Since 2020, the community around the algebraic approach to CSP has met yearly at the so-called CSP World Congress. The categorical approach to automata theory and formal languages concentrates around the Conference on Algebra and Coalgebra in Computer Science (CALCO), held every odd year since 2005, and the Workshop on Coalgebraic Methods in Computer Science (CMCS), held every even year. Also, in 2025, there was a Dagstuhl workshop called Categories for Automata and Language Theory aimed at the same community.

However, our scope is wider than these events. It follows the tradition of the one- and two-day Structure meets Power series of workshops, see 2026, 2024, 2023, 2022, 2021. Unlike with the Structure meets Power workshop, which are typically short, this workshop is a dedicated multi-day workshop designed to provide more space for interaction.

Organisers

• Tomáš Jakl, Czech Technical University
• Dan Marsden, University of Nottingham

Acknowledgement

The workshop is funded by the EU’s Horizon Europe research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101111373.