**Categories for Automata and Language Theory @ IRIF** a working group * Categorical methods have a long history in automata and language theory, but only in recent years a coherent theory has started to emerge. Among them, there are now monadic, coalgebraic, functorial, fibrational and profinite approaches to automata. The purpose of this working group is to discuss these approaches, the connections between them, and their applications to questions in automata and language theory. * We meet every two weeks on **Tuesday** at **10:30** in room **1020** at [IRIF](https://www.irif.fr/), bâtiment Sophie Germain, pl. Aurélie Nemours, 75013 Paris, France ([map](https://goo.gl/maps/GNZ7y45a9uqDWzea9)). * To receive email announcements about future meetings, you can subscribe to our [mailing list](https://sympa.lix.polytechnique.fr/lists/info/autcat). Future ============================== * Idea from Noam to at some point also discuss: [Steinberg 2001](https://www.ams.org/journals/tran/2001-353-09/S0002-9947-01-02774-X/S0002-9947-01-02774-X.pdf) 30 April 2024, 10h30-12h30 =============================== **Room 1020** * Serge Lechenne: A Compositional Approach to Petri Nets _Abstract: We define a bidirectional compositional framework for Petri nets based on a line of work about compositionally defining games and computation models. This relies on defining structures with open ends that form interfaces they can be composed along. Together with this syntactic construction, we give a graphical language of morphisms in a PROP and a semantic category that describes the evolution of markings in a Petri net. Compared to previous work, the novelty is that computations in a Petri net are stateful, requiring specific care. We give algorithms to solve reachability compositionally in this framework._ 23 April 2024, 10h30-12h30 =============================== * Quentin told us more about the multicategorical framework for minimization and learning of bottom-up tree automata 16 April 2024, 10h30-12h30 =============================== **Room 1020** * Quentin: Multicategorical framework for minimization and learning of bottom-up tree automata with effects + Paper: to be uploaded to HAL 2 April 2024, 10h30-12h30 =============================== **Room 1020** * Daniela: a categorical approach to learning automata and transducers. See [CSL 2021 paper](https://drops.dagstuhl.de/storage/00lipics/lipics-vol183-csl2021/LIPIcs.CSL.2021.15/LIPIcs.CSL.2021.15.pdf). 26 March 2024, 10h30-12h30 =============================== **Room 1020** * Jérémie: a categorical (and graphical) viewpoint on the theory of Green relations. Also see Chapter 6 of [Jérémie's thesis](https://jeremie-marques.name/papers/thesis.pdf). 12 March 2024, 10h30-12h30 =============================== **Room 1020** * Quentin gave an introduction to coalgebraic modal mu calculus. 5 March 2024 =============================== **Room 1020**, 10h30-12h30. * Sam: Polyadic spaces and hyperdoctrines, and the relationship with logic on words. The [slides](./gool-autcat2024-slides.pdf), and some references: + [Ch. 5 of Jérémie's PhD thesis](https://jeremie-marques.name/papers/thesis.pdf) + [Our recent paper on polyadic spaces and hyperdoctrines](https://www.sciencedirect.com/science/article/pii/S0168007223001458) 27 February 2024 =============================== **Room 1020**, 10h30-12h30 (note new Tuesday morning time slot) * Jérémie: continuation of talk from 1 Feb, with discussion of [Monadic Monadic (sic) Second Order Logic](https://arxiv.org/abs/2201.09969). 1 February 2024 =============================== **Room 3052**, 14h * Jérémie: Eilenberg's theorem and duality * Literature: [Marquès RAMICS 2019](https://jeremie-marques.name/papers/duality_monoids.pdf) and [Urbat et al. MFCS 2017](https://arxiv.org/abs/1602.05831) 11 January 2024 =============================== **Room 3052**, 14h * [Tito](https://nguyentito.eu/): categorical perspectives on regular string-to-string functions, namely * streaming string transducers (SSTs) in the Thomas-Daniela functorial framework + sketch of monoidal closure for a variant of the category (j.w.w. Cécilia, [arXiv:2008.01050](https://arxiv.org/abs/2008.01050)) * algebraic recognition via semigroup endofunctors (j.w.w. Mikołaj, [hal-03985883](https://hal.science/hal-03985883)) * discussion of connections between the two (internal homs lead to internal semigroups...) 7 December 2023 =============================== **Room 1007, 14h-16h** * Thomas: monadic tutorial * **Literature:** [Bojańczyk 2015](https://arxiv.org/abs/1502.04898) * Topics discussed: * Definition of recognizability wrt a monad * How it applies in the case of countable linear words * And in the case of countable ordinal words, where we can get effective computations * There the "finitary completeness" of omega-terms inside the full set of countable ordinal words is important. * Also mentioned: [Klin Bojańczyk Salamanca 2023](https://www.cs.ox.ac.uk/people/bartek.klin/papers/samson23.pdf) 23 November 2023 =============================== **Room 3052, 12h-14h** (Gaëtan Douéneau's [PhD defense](https://gdoueneau.github.io/pages/phd.html) at 14h) * Quentin: functorial tutorial * **Literature:** [Colcombet Petrişan 2020](https://lmcs.episciences.org/6213) 9 November 2023 =============================== **Room 1007, 14h-16h** * What do we want to do? - Chomsky-Schutzenberger theorem, categorical view - Combining Wilke algebras and semiring-modules, via the functorial approach - Monadic approach to infinite words (and trees) * How do we want to do it? - Meeting every other week, beginning with "tutorial" introductions to the various categorical frameworks. - List papers online. 26 October 2023 =============================== **14h-16h** * Discussions about organization and preparation of proposal. * A universal property for $\epsilon$-elimination in automata. 12 October 2023 =============================== **11h30-13h30** * Unique lifting property, equidivisibility. 28 September 2023 =============================== **14h-16h** * The fibrational view on automata and transducers * Direct image of regular languages under letter-to-letter morphisms are regular: is there a categorical proof? * We made a list of topics/keywords that we might discuss at some point: - factorization systems and decompositions - higher-order specifications - Kleene's theorem - relating bifibrations of languages to opfibrations of automata - trees, Safra construction - $\mu$-calculus and MSO, and the algebras for them - topological recognizers and Boolean spaces with internal monoids # Participants * [Quentin Aristote](https://quentin.aristote.fr/) * [Thomas Colcombet](https://www.irif.fr/~colcombe) * [Sam van Gool](https://www.samvangool.net) * Victor Iwaniack * [Roman Kniazev](https://www.irif.fr/~kniazev/) * Thea Li * [Jérémie Marquès](https://www.jeremie-marques.name/) * [Paul-André Melliès](https://www.irif.fr/~mellies) * [Daniela Petrisan](https://www.irif.fr/~petrisan) * [Noam Zeilberger](https://www.noamz.org)