19 April 2018, ILLC Seminar, Daniela Petrisan

In this talk I will present an overview of some recent results involving applications of duality and category theory in automata and language theory.

One such strand of research involves a generic approach to  automata minimization. We depart from the standard coalgebraic approach and model automata as functors from a category specifying the input of the machine to another category which captures the structure of it's output. We identify sufficient conditions on the output category which ensure the existence of minimal automata. This allows us to cover awide range of examples by systematically applying the same category-theoretic principles in various instances.

A second research axis heavily uses duality theory to extend algebraic methods from the theory of regular languages to the non-regular setting. There are a plethora of results relating algebraic and logical characterizations of classes of regular languages. We aim to develop the tools that allow us to obtain such correspondences forclasses of non-regular languages. I will explain in detail how thesyntactic monoid of a language can be seen as the dual of the Booleanalgebra spanned by the quotients of that language. This paves the way for defining a suitable notion of recognisers for non-regular languages and to extend in this setting standard constructions from monoids that are the algebraic counterpart of logical quantifiers.