**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 generally every two weeks on **Friday** at **10:30** at [IRIF](https://www.irif.fr/), bâtiment Sophie Germain, pl. Aurélie Nemours, 75013 Paris, France ([map](https://goo.gl/maps/GNZ7y45a9uqDWzea9)). See below for the precise room. A calendar of the sessions can be found [here](https://cloud.irif.fr/remote.php/dav/public-calendars/ADSGntbwqxbDANYM?export). * To receive email announcements about future meetings, you can subscribe to our [mailing list](https://sympa.lix.polytechnique.fr/lists/info/autcat). Future ============================== We would like to at some point read and discuss: * [Steinberg 2001](https://www.ams.org/journals/tran/2001-353-09/S0002-9947-01-02774-X/S0002-9947-01-02774-X.pdf) * [Hyland 2008](https://www.dpmms.cam.ac.uk/~martin/Research/Publications/2008/acmr08.pdf) 8 November 2024, 10h30-12h30 =============================== **Room 3063** * [Paul-André Melliès](https://www.irif.fr/~mellies/) TBA 18 October 2024 =============================== All day: [Seminaire itinerant des categories](https://www-lmpa.univ-littoral.fr/~sic/wordpress/?page_id=1405) 11 October 2024, 10h30-12h30 =============================== **Room 3063** * [Joshua Wrigley](https://jlwrigley.github.io/): **A topos-theoretic perspective on completions of doctrines** Abstract: Lawvere doctrines are an intuitive extension of Lindenbaum-Tarski algebras from propositional logic to predicate logic, where the role of logical quantifiers is captured by a pair of adjoint functions. In recent years, there has been increasing interest in the field of ‘completing’ doctrines to richer syntax, e.g. Trotta’s existential completion. We will describe a topos-theoretic framework for completing doctrines to subfragments of geometric logic. 4 October 2024, 10h30-12h30 =============================== **Room 3063** * Brainstorm on what we would like to discuss this year. Ideas and things discussed during this meeting: * Christol theorem and categories (Paul-André) * Languages of λ-terms and fibrations, Frobenius reciprocity (Paul-André & Vincent) * MSO on finite graphs (Thomas Colcombet) * Finite semigroup theory and derived categories, reading Tilson's [Categories as algebra](https://www.sciencedirect.com/science/article/pii/0022404987901083) (Sam) * Learning automata over number fields (Quentin, Sam, Mahsa, Daniela) * Compactification and weak distributive laws (Quentin, Daniela) * Automata in toposes (Victor Iwaniack) * Formalizations of automata theory? * Context-free grammars, a categorical invariant? (Noam) * Ultracategories and compactness theorems in logic 11 June 2024, 10h30-12h30 =============================== **Room 4071** * Victor Iwaniack: Automata in W-Toposes, and General Myhill-Nerode Theorems 4 & 5 June 2024 =============================== [LHC days](https://smimram.gitlabpages.inria.fr/lhc/journees.html) 21 May 2024, 10h30-12h30 =============================== **Room 4071** * Vincent: profinite trees 7 May 2024, 10h30-12h30 =============================== **Room 4071** * Noam: Context-free languages as initial models of context-free grammars. See "Addendum A" of [our recent preprint](https://hal.science/hal-04399404). 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._ + [CMCS 2024 preprint](https://www.coalg.org/cmcs24/papers/5-lechenneEA.pdf) 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) * [Vincent Moreau](https://www.irif.fr/~moreau) * [Daniela Petrisan](https://www.irif.fr/~petrisan) * [Noam Zeilberger](https://www.noamz.org)