Eilenberg's theorem for positive varieties of languages
type: Item
instance of: scholarly article
title: Eilenberg's theorem for positive varieties of languages
zbMATH Open document ID: 0852.20059
author: Jean-Éric Pin
published in: Russian Mathematics
publication date: 1996-05-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 08C15
Mathematics Subject Classification ID: 06F05
Mathematics Subject Classification ID: 20M07
zbMATH DE Number: 862282
zbMATH Keywords: Eilenberg's theorem
zbMATH Keywords: pseudovarieties of finite semigroups
zbMATH Keywords: varieties of recognizable languages
zbMATH Keywords: positive varieties of languages
zbMATH Keywords: pseudovarieties of finite ordered semigroups
reviewed by: Leonid M. Martynov
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 862282