A variety theorem without complementation

J-E. Pin

IBP-Litp 1994/45: Rapport de Recherche Litp / Litp research reports
12 pages - Décembre/December 1994 - Document en anglais.

Titre / Title: A variety theorem without complementation

Résumé : Le théorème d'Eilenberg est un outil important de la théorie des langages. Il établit une correspondance bijective entre les variétés de semigroupes finis et les variétés de langages, qui sont des classes de langages reconnaissables fermées pour les opérations booléennnes finies, les morphismes inverses et les résiduels. Le but de cet article est d'établir un résultat analogue, mais pour des classes plus générales que les variétés de langages. On applelle variété positive de langages une classe de langages reconnaissables fermée par union finie, intersection finie, morphisme inverse et résiduels. On démontre dans cet article que les variétés positives sont en correspondance bijective avec les variétés de semigroupes ordonnés. On donne ensuite plusieurs exemples de cette correspondance.

Abstract : Eilenberg's theorem is an important tool in the theory of languages. It gives a one to one correspondence between varieties of finite semigroups and varieties of languages, which are classes of languages closed under finite boolean operations, inverse morphisms and residuals. The aim of this paper is to prove a similar result for a larger class than varieties of languages. A positive variety is a class of recognizable languages closed under finite union, finite intersection, inverse morphism and residuals. It is shown in this paper that positive varieties are in one to one correspondence with varieties of finite ordered semigroups. Several examples of this correspondence are given.

Publications internes Litp 1994 / Litp research reports 1994