**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 **Thursday**, usually at **14:00**, 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) * [v. Gool & Marquès 2023](https://arxiv.org/abs/2210.01018) 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 Second Order Logic. 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)