Generalized Eilenberg Theorem: Varieties of Languages in a Category

摘要

For finite automata as coalgebras in a category C, we study languages they accept and varieties of such languages. This generalizes Eilenberg's concept of a variety of languages, which corresponds to choosing as C the category of Boolean algebras. Eilenberg established a bijective correspondence between pseudovarieties of monoids and varieties of regular languages. In our generalization, we work with a pair C/D of locally finite varieties of algebras that are predual, i.e., dualize, on the level of finite algebras, and we prove that pseudovarieties D-monoids bijectively correspond to varieties of regular languages in C. As one instance, Eilenberg's result is recovered by choosing D = sets and C = Boolean algebras. Another instance, Pin's result on pseudovarieties of ordered monoids, is covered by taking D = posets and C = distributive lattices. By choosing as C = D the self-predual category of join-semilattices, we obtain Polak's result on pseudovarieties of idempotent semirings. Similarly, using the self-preduality of vector spaces over a finite field K, our result covers that of Reutenauer on pseudovarieties of K-algebras. Several new variants of Eilenberg's theorem arise by taking other predualities, e.g., between the categories of non-unital Boolean rings and of pointed sets. In each of these cases, we also prove a local variant of the bijection, where a fixed alphabet is assumed and one considers local varieties of regular languages over that alphabet in the category C.