A classification of rational languages by semilattice-ordered monoids

Libor Polak

  Department of Mathematics, Masaryk University, Janackovo nam. 2a, 662 95 Brno, Czech Republic

E-mail. polak@math.muni.cz

We prove here an Eilenberg type theorem: the so-called conjunctive varieties of rational languages correspond to the pseudovarieties of finite semilattice-ordered monoids. Taking complements of members of a conjunctive variety of languages we get a so-called disjunctive variety. We present here a non-trivial example of such a variety together with an equational characterization of the corresponding pseudovariety.

AMSclassification. Primary: 68Q70; Secondary: 20M07, 06F05.

Keywords.  Syntactic semilattice-ordered monoid, conjunctive varieties of rational languages.