Formations of finite monoids and formal languages: Eilenberg's variety theorem revisited. (Q470234)

A \textit{formation of monoids} is a class of finite monoids closed under taking quotients and finite subdirect products. A language is a subset of a free monoid \(A^*\) where \(A\) is a finite alphabet. A language is recognizable (or regular) if it is recognized by a finite deterministic automaton. Recall that the syntactic monoid of a language \(L\) of \(A^*\) is the quotient of \(A^*\) by the syntactic congruence of \(L\), defined on \(A\) as follows: \(u\sim_Lv\) if and only if, for every \(x,y\in A^*\) , \(xvy\in L\Leftrightarrow xuy\in L\). The natural morphism \(\eta\colon A^*\to A /\sim_L\) is the syntactic morphism of \(L\). A class of regular languages \(\mathcal C\) associates with each finite alphabet \(A\) a set \(\mathcal C(A^*)\) of regular languages of \(A^*\). A \textit{formation of languages} is a class of regular languages \(\mathcal F\) satisfying the following conditions: \((F_1)\) for each alphabet \(A\), \(\mathcal F(A)\) is closed under Boolean operations and quotients, \((F_2)\) if \(L\) is a language of \(\mathcal F(B^*)\) and \(\eta\colon B^*\to M\) denotes its syntactic morphism, then for each monoid morphism \(\alpha\colon B^*\to A^*\) such that \(\eta\circ\alpha\) is surjective, the language \(\alpha^{-1}(L)\) belongs to \(\mathcal F(A^*)\). The authors present an extension of the well-known Eilenberg's theorem (connecting pseudovarieties of monoids and streams of regular languages) on formations of finite monoids and languages. They prove that there is a bijective correspondence between formations of finite monoids and the formations of languages. This result permits to treat classes of finite monoids which are not necessarily closed under taking submonoids, contrary to the original theory. The authors also prove a similar result for ordered monoids.