Automata Minimization: a Functorial Approach

In this talk I will present a categorical approach to automata minimization. We regard automata (or more generally language recognisers) as functors from a category  that captures the structure of the input (words, monoids, trees) to another category that models the type of the automata (deterministic, non-deterministic, weighted, transducers etc). We show how to obtaining a unifying framework for understanding various well-known phenomena in automata theory. Examples include the usual minimization of DFAs, of weighted automata over a field, of subsequential transducers, but also syntactic algebras for regular languages and  the syntactic Boolean space with an internal monoid for a non-regular language.This is joint work with Thomas Colcombet.