Recognizing Languages with Finite Monoidal Categories

A classic result of language theory [Eilenberg, Proposition 12.3] characterizes recognizable word languages as those whose characteristic functions are representative functions [Griffing] -- the latter playing a seminal role in the theory of Hopf algebras [Sweedler]. The guiding question of the talk is whether Eilenberg's characterization of recognizability extends to languages of forests if we replace composition of words by grafting of forests (taking preclones as formal background).

The second half of Eilenberg's proof, which relies solely on finite monoids as language recognizers, carries over to finite monoidal categories: the ensuing *functorially recognizable* languages of arrows in a monoidal category thus have representative characteristic functions. Moreover, forest languages that are star-free in a ``Schützenbergerian'' way are functorially recognizable, which makes functorial recognizability a non-trivial concept. Finally, the main motivation to study functorial recognizability is the canonical notion of (non-trivial) groupoids in monoidal categories, which nourishes the hope that Schützenberger's characterization of star-free word languages [Schütz] lifts to tree and forest languages.

[Eilenberg] Eilenberg, Samuel. ``Automata, languages, and machines.'' Pure and Applied Mathematics, Volume 59, Part A (1974).
[Griffing] Griffing, Gary. ``Composition-representative subsets.'' Theory and Applications of Categories 11.19 (2003).
[Schütz], Schützenberger, Marcel Paul. ``On finite monoids having only trivial subgroups.'' Information and Control 8.2 (1965).
[Sweedler] Sweedler, Moss E., ``Hopf Algebras.'' Mathematics Lecture Note Series, Volume 44 (1969).