Eilenberg's theorem for positive varieties of languages (Q1910276)

The most important tool for classifying recognizable languages is Eilenberg's theorem, which gives a one-to-one correspondence between pseudovarieties of finite semigroups and varieties of recognizable languages (i.e., the classes of recognizable languages closed under finite union, finite intersection, complement, left and right quotients, and inverse morphisms). Recall that one passes from a language to a finite semigroup by computing its syntactic semigroup. However, certain interesting families of recognizable languages, not being varieties of languages, admit a syntactic characterization. The aim of the article is to show that such results are instances of a certain regularity as general as Eilenberg's theorem. On the language side, positive varieties of languages (i.e., classes of recognizable languages which have the same properties as the varieties of languages except these are not supposed to be closed under complement) are considered. On the algebraic side, the pseudovarieties of finite semigroups are replaced by the pseudovarieties of finite ordered semigroups. The main result states a one-to-one correspondence between the positive varieties of languages and the pseudovarieties of finite ordered semigroups. The proof of the main result is inspired by the proof of Eilenberg's theorem, although there are some subtle adjustments to do. It is noted that the monoid version of the main result of the article is true. Certain examples are presented. Namely, the languages which are recognized by one of the following semigroups: finite ordered nilpotent semigroups in which 0 is the smallest element; finite ordered semilattices with 1 in which 1 is the greatest element; finite ordered monoids in which 1 is the greatest element; are described.