Eilenberg theorems for many-sorted formations

Abstract

A theorem of Eilenberg establishes that there exists a bijection between the set of all varieties of regular languages and the set of all varieties of finite monoids. In this article after defining, for a fixed set of sorts $S$ and a fixed $S$-sorted signature $\Sigma$, the concepts of formation of congruences with respect to $\Sigma$ and of formation of $\Sigma$-algebras, we prove that the algebraic lattices of all $\Sigma$-congruence formations and of all $\Sigma$-algebra formations are isomorphic, which is an Eilenberg's type theorem. Moreover, under a suitable condition on the free $\Sigma$-algebras and after defining the concepts of formation of congruences of finite index with respect to $\Sigma$, of formation of finite $\Sigma$-algebras, and of formation of regular languages with respect to $\Sigma$, we prove that the algebraic lattices of all $\Sigma$-finite index congruence formations, of all $\Sigma$-finite algebra formations, and of all $\Sigma$-regular language formations are isomorphic, which is also an Eilenberg's type theorem.

46 pages

Cited by in corpus (1)

• Congruence based proofs of the recognizability theorems for free many-sorted algebras