On pseudovarieties of morphisms
by
Libor Polák
Dept. Mathematics, Masaryk University Brno

By the classical Eilenberg Theorem the so-called varieties of regular languages correspond to pseudovarieties of monoids. The passage from languages to monoids is done by taking syntactic monoids. An independent approach uses pseudovarieties of idempotent semirings and syntactic semirings.

Let C be a category of finitely generated free monoids. Following Straubing a C-pseudovariety of monoid morphism is a class of morphisms from finitely generated free monoids onto finite monoids which is closed with respect to certain operators (related to classical H, S, P). He proved also an Eilenberg-type theorem. Here one assigns to a language the whole syntactic morphism.

A Reiterman-type theorem for such pseudovarieties was established by Kunc. In fact the pseudoidentities are exactly the classical ones, the concept of satisfaction depends on the category C.

We can define D-pseudovarieties of semiring morphisms in a similar way. It is also possible to formulate and prove Eilenberg- and Reiterman-type theorems.

We iniciate a systematic study of C-pseudovarieties of monoid morphisms and D-pseudovarieties of semiring morphisms.

Date received: May 20, 2004