×

zbMATH — the first resource for mathematics

A classification of rational languages by semilattice-ordered monoids. (English) Zbl 1112.68098
In this paper, an Eilenberg-type theorem is proved. In the classical Eilenberg theorem, Boolean varieties of rational languages correspond to pseudovarieties of finite monoids. In Pin’s generalization of this theorem, positive varieties of rational languages correspond to pseudovarieties of finite ordered monoids. In the present paper, it is shown that the so-called conjunctive varieties of rational languages correspond to the pseudovarieties of finite semilattice-ordered monoids. A conjunctive variety of rational languages is a class of rational languages over finite alphabets which is closed under finite intersections, left and right quotients and inverse images with respect to homomorphisms of the free semilattice-ordered monoids over the given finite alphabets. Semilattice-ordered monoids are more commonly called idempotent semirings.

MSC:
68Q70 Algebraic theory of languages and automata
20M07 Varieties and pseudovarieties of semigroups
06F05 Ordered semigroups and monoids
08A70 Applications of universal algebra in computer science
16Y60 Semirings
PDF BibTeX XML Cite
Full Text: EMIS EuDML