Dagstuhl Seminar 25141
Categories for Automata and Language Theory
( Mar 30 – Apr 04, 2025 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/25141
Organizers
- Achim Blumensath (Masaryk University - Brno, CZ)
- Mikolaj Bojanczyk (University of Warsaw, PL)
- Bartek Klin (University of Oxford, GB)
- Daniela Petrisan (Université Paris Cité, FR)
Contact
- Andreas Dolzmann (for scientific matters)
- Jutka Gasiorowski (for administrative matters)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
Categorical methods have a long history in automata and language theory (see, e.g., [1, 2, 3, 4, 5] for early examples), but only in recent years a coherent theory has started to emerge. As an indication of the increasing popularity, note that papers on categories and automata have regularly appeared in the last three years, both at ICALP(B) and at LICS. These are the top conferences in the field of Track B of Theoretical Computer Science, but a similar pattern holds across other conferences in this field. There are several reasons why these abstract approaches have become popular in automata theory.
- They provide a unifying perspective on various forms of automata. For example, minimisation and learning algorithms for deterministic automata, weighted automata and sequential transducers can be seen as instances of a generic algorithm given at an abstract category-theoretic level [6].
- They make it easier to bootstrap a theory in a new setting. For instance, one of the main motivations of the monadic approach to recognisability [7] was to extend the existing algebraic theories to infinite trees [8].
- They provide conceptual clarity regarding which aspects and properties are fundamental and which are only coincidental. For example, the semiring based formalism to formal languages treats addition and multiplication symmetrically, while a more general approach [9] reveals that multiplication is specific to the shapes of the objects in question while addition is universal and related to the power-set operation.
The field is still in its early stages, and as a result it is still divided into several different communities with little connections between them. The purpose of this Dagstuhl Seminar was to connect researchers active in these communities; to make them aware of the work of other groups; to initiate collaborations; and to discuss recent developments and possible ways to go forward.
Organization of the seminar
The organisers designed the schedule to strike a balance between survey talks, focused presentations, and free time for informal discussions. Participants were encouraged to share their work and highlight recent advances in their respective fields. Given the diverse backgrounds of the attendees, the organisers invited several participants to deliver extended tutorial-style talks on specific topics to help bridge disciplinary gaps. Five such talks were presented, as listed below.
- Achim Blumensath: Monads and Recognisability. This tutorial aims to provide an accessible introduction and a broad overview of a recently developed framework for algebraic language theory, which is based on monads and Eilenberg–Moore algebras.
- Mikolaj Bojańczyk: The Composition Method. This talk explores the connection between algebra and logic through a categorical lens intended to support generalisations beyond word languages, but from a viewpoint dual to the one adopted in the first tutorial: logic serves as the primary notion, and algebraic structures are derived from it. The central topic of interest is the category of MSO-transductions.
- Pawel Sobocinski: String Diagrams. The talk introduced string diagrams – a mathematical notation rooted in (monoidal) category theory – and its applications through computer science. In particular, it discussed monoidal automata and their languages of string diagrams.
- Yde Venema: Coalgebra. The talk offered a gentle introduction to universal coalgebra as a broad categorical framework for modeling state-based evolving systems. It discussed coinduction, behavioral equivalence and bisimilarity.
- Noam Zeilberger A tutorial on (generalized) fibrations for logic, automata and language theory. The talk provided an introduction to certain fibrational concepts from category theory and their relevance to addressing “lifting problems” in logic, automata, and language theory.
Apart from the tutorials, 30 other participants delivered short presentations on recent work related to the topics listed above. Two additional sessions were set aside to allow time for informal discussions and interactions.
Conclusions
The organizers considered the seminar to be a success. Most participants reported gaining new insights from other areas and many expressed interest in applying these ideas to advance their own research. Among the participants who filled in the survey, more than half evaluated the scientific quality of the seminar as outstanding. We have striven to integrate junior researchers and many of them gave talks. This came at the expense of having less time dedicated to personal interactions.
References
- P. L. F. Rudolf E. Kalman and M. A. Arbib, Topics in Mathematical System Theory, McGraw-Hill, 1969.
- S. Eilenberg, Automata, Languages, and Machines: volume A, Pure and applied mathematics, Academic Press, 1974.
- M. A. Arbib and E. G. Manes, A categorist’s view of automata and systems, in Category Theory Applied to Computation and Control, Proceedings of the First International Symposium, San Francisco, CA, USA, February 25–26, 1974, Proceedings, E. G. Manes, ed., vol. 25 of Lecture Notes in Computer Science, Springer, 1974, pp. 51–64.
- H. Ehrig, K. Kiermeier, H. Kreowski, and W. Kühnel, Universal theory of automata. A categorial approach, Teubner Studienbücher, Teubner, 1974.
- B. Tilson, Categories as algebra: An essential ingredient in the theory of monoids, Journal of Pure and Applied Algebra, 48 (1987), pp. 83–198.
- T. Colcombet, D. Petrişan, and R. Stabile, Learning automata and transducers: A categorical approach, in 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25–28, 2021, Ljubljana, Slovenia (Virtual Conference), C. Baier and J. Goubault-Larrecq, eds., vol. 183 of LIPIcs, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, pp. 15:1– 15:17.
- M. Bojańczyk, Recognisable languages over monads. Unpublished note, arXiv:1502.04898v1.
- Regular Tree Algebras, Logical Methods in Computer Science, 16 (2020), pp. 16:1–16:25.
- The Power-Set Operation for Tree Algebras, Logical Methods in Computer Science, (to appear).
Creative Commons BY 4.0
Achim Blumensath, Mikolaj Bojanczyk, Bartek Klin, and Daniela Petrisan
Categorical methods have a long history in automata and language theory, but a coherent theory has started to emerge only in recent years. Some recent examples of categorical methods in automata theory include monadic, coalgebraic, functorial, fibrational and profinite approaches. Such an abstract viewpoint can provide a unifying perspective on various forms of automata; it can make it easier to bootstrap a theory in a new setting; and it provides conceptual clarity regarding which aspects and properties are fundamental and which are only coincidental.
Due to being in its early stages, the field is currently still divided into several different communities with little connections between them. The purpose of this seminar is to connect these communities; to initiate collaborations; and to discuss recent developments and possible ways to go forward. The seminar will mix researchers of different backgrounds, in order to achieve a healthy balance between abstraction and applications in automata theory.
We hope that the meeting will foster further interaction between the different communities. It should benefit category theorists, who may or may not have studied computation theory before, by inspiring them to look at problems motivated by automata and formal languages. It should also be useful to automata theorists, who may or may not be familiar with categorical techniques, by exposing them to the scope and strength of these techniques. We hope that this interaction will be both productive and enjoyable for all participants.
Achim Blumensath, Mikolaj Bojanczyk, Bartek Klin, and Daniela Petrisan
Please log in to DOOR to see more details.
- Samson Abramsky (University College London, GB) [dblp]
- Bahareh Afshari (University of Gothenburg, SE) [dblp]
- Quentin Aristote (IRIF - Paris, FR)
- Achim Blumensath (Masaryk University - Brno, CZ) [dblp]
- Mikolaj Bojanczyk (University of Warsaw, PL) [dblp]
- Célia Borlido (University of Coimbra, PT) [dblp]
- Thomas Colcombet (IRIF - CNRS - Université Paris Cité, FR) [dblp]
- Ugo Dal Lago (University of Bologna, IT) [dblp]
- Elena Di Lavore (University of Pisa, IT) [dblp]
- Matthew David Earnshaw (Tallinn University of Technology, EE)
- Uli Fahrenberg (EPITA - Cesson-Sévigné, FR) [dblp]
- Zeinab Galal (University of Bologna, IT)
- Silvio Ghilardi (University of Milan, IT) [dblp]
- Helle Hvid Hansen (University of Groningen, NL) [dblp]
- Victor Iwaniack (University of Côte d’Azur - Nice, FR)
- Tomas Jakl (Czech Technical University - Prague, CZ) [dblp]
- Bartek Klin (University of Oxford, GB) [dblp]
- Barbara König (Universität Duisburg-Essen, DE) [dblp]
- Aliaume Lopez (University of Warsaw, PL)
- Fosco Loregian (Tallinn University of Technology, EE)
- Jérémie Marquès (University of Milan, IT)
- Paul-Andre Mellies (Université Paris Cité, FR) [dblp]
- Karla Messing (Universität Duisburg-Essen, DE)
- Stefan Milius (Universität Erlangen-Nürnberg, DE) [dblp]
- Vincent Moreau (Université Paris Cité, FR)
- Rémi Morvan (University of Bordeaux, FR) [dblp]
- Andrzej Murawski (University of Oxford, GB) [dblp]
- Lê Thành Dung Nguyen (CNRS & Aix-Marseille Univ., FR) [dblp]
- Jakub Opršal (University of Birmingham, GB) [dblp]
- Daniela Petrisan (Université Paris Cité, FR) [dblp]
- Cécilia Pradic (Swansea University, GB) [dblp]
- Jurriaan Rot (Radboud University Nijmegen, NL) [dblp]
- Lutz Schröder (Universität Erlangen-Nürnberg, DE) [dblp]
- Tim Seppelt (IT University of Copenhagen, DK)
- Nihil Shah (University of Cambridge, GB) [dblp]
- Ryoma Sin'ya (Akita University, JP) [dblp]
- Pawel Sobocinski (Tallinn University of Technology, EE) [dblp]
- Ana Sokolova (Paris Lodron Universität Salzburg, AT) [dblp]
- Rafal Stefanski (University of Warsaw, PL) [dblp]
- Howard Straubing (Boston College, US) [dblp]
- Henning Urbat (Universität Erlangen-Nürnberg, DE) [dblp]
- Sam van Gool (Université Paris Cité, FR) [dblp]
- Yde Venema (University of Amsterdam, NL) [dblp]
- Jana Wagemaker (Radboud University Nijmegen, NL)
- Noam Zeilberger (Ecole Polytechnique - Palaiseau, FR)
- Krzysztof Ziemianski (University of Warsaw, PL) [dblp]
Classification
- Formal Languages and Automata Theory
- Logic in Computer Science
Keywords
- category theory
- automata
- formal language theory
