Classification of regular languages by congruences
Denis Thérien · 1980
In this thesis, we consider the problem of providing an algebraic classification of regular languages. An abstract monoid M recognizes the language L (L-HOOK EQ) A* iff there exists a surjective morphism (phi): A* (--->) M such that L = S(phi)('-1) for some S (L-HOOK EQ) M. Given a family M of abstract monoids, it is a natural problem to try to characterize the languages recognized by the monoids in M. Conversely, given a family of languages , we can ask for a characterization of the smallest family of monoids which are needed to recognize all the languages in . A family M of finite monoids is a variety iff it is closed under morphic images, submonoids and finite direct products. A family of regular languages is a *-variety iff it is closed under boolean operations, derivatives and inverse morphisms. Eilenberg's theorem indicates that there exists a 1-1 correspondence between varieties of monoids and *-varieties of languages. Our approach makes use of congruences of finite index. The conditions defining varieties are first expressed in terms of these objects. We then present a method for constructing congruences which generates *-varieties in a systematic manner. The languages produced in this way have the property that the membership of a word x can be determined by counting occurrences of subwords of length (LESSTHEQ) m with respect to a congruence of finite index on IN, taking into account the context in which these subwords appear with respect to a previously given congruence (gamma). This scheme is recursively applied, using as basis the universal congruence x (omega) y for all x, y (epsilon) A*. Noting the fact that every congruence of finite index on IN is the intersection of a threshold t counting congruence and a modulo q counting congruence, our *-varieties of congruences are characterized by four parameters: the t and q of the congruence on IN with respect to which the counting is done, the length m of the subwords that are counted and the depth i of the recursion. Algebraic properties of the corresponding monoids are then investigated in terms of these four indices. For all values of m and i, if only threshold t counting is used (i.e. q is fixed to 1), the generated monoids are aperiodic, and if only modulo q counting is used (i.e. t is fixed to 0), the generated monoids are groups. The following table summarizes some characterizations that have been obtained.^ i = 1, m = 1, t (GREATERTHEQ) 0, q = 1 commutative aperiodic monoids i = 1, m = 1, t = 0, q (GREATERTHEQ) 1 commutative groups i = 1, m = 1, t (GREATERTHEQ) 0, q (GREATERTHEQ) 1 commutative monoids i = 1, m (GREATERTHEQ) 0, t (GREATERTHEQ) 0, q = 1 J-trivial monoids i = 1, m (GREATERTHEQ) 0, t = 0, q (GREATERTHEQ) 1 nilpotent groups i = n, m = 1, t = 0, q (GREATERTHEQ) 1 solvable groups of derived length (LESSTHEQ) n i = n, m (GREATERTHEQ) 0, t = 0, q (GREATERTHEQ) 1 solvable groups of fitting length (LESSTHEQ) n i (GREATERTHEQ) 0, m = 1, t (GREATERTHEQ) 0, q = 1 aperiodic monoids i (GREATERTHEQ) 0, m = 1, t = 0, q (GREATERTHEQ) 1 solvable groups i (GREATERTHEQ) 0, m = 1, t (GREATERTHEQ) 0, q (GREATERTHEQ) 1 monoids containing only solvable groups.^ For the last three entries, the monoids are the same if we replace m = 1 by m (GREATERTHEQ) 0. In several other cases partial characterizations are presented. In addition, tradeoffs between the various parameters are analyzed and some families of languages are investigated from the point of view of Kleene's operations. Finally, modifying the construction to take into account one-sided contexts only, it is shown that R and L-trivial monoids are generated when threshold t counting is used.