Positive varieties and infinite words

Jean-Éric Pin

PostScript file compressed with gzip, PDF file
Résumé : Parachevant les travaux d'Arnold, Pécuchet et Perrin, Wilke a obtenu un analogue du théorème des variétés d'Eilenberg pour les mots infinis. Dans cet article, nous étendons cette théorie à des classes de langages qui sont fermées par union et intersection, mais pas nécessairement par complément. A titre d'exemple, nous donnons une caractérisation purement algébrique de diverses classes de parties reconnaissables définies par des propriétés algébriques (ouverts, fermés, F&sigma et G&delta) ou par des propriétés combinatoires.
Abstract : Carrying on the work of Arnold, Pécuchet and Perrin, Wilke has obtained a counterpart of Eilenberg's variety theorem for finite and infinite words. In this paper, we extend this theory for classes of languages that are closed under union and intersection, but not necessarily under complement. As an example, we give a purely algebraic haracterization of various classes of recognizable sets defined by topological properties (open, closed, F&sigma and G&delta) or by combinatorial properties.

Résumé étendu : Cet article est une contribution à la théorie des langages de mots infinis, ou ω-langages. Jusqu'à présent, cette théorie a réussi à étendre la plupart des résultats connus sur les mots finis au mots infinis, ce qui ne veut pas dire que ces extensions soient triviales. Le meilleur exemple en est l'équivalence entre automates finis déterministes et non déterministes. Le résultat est relativement facile pour les langages, mais devient assez astucieux pour les ω-langages. En effet, si on se contente de la conditions d'acceptation introduite par Büchi, il y a une relation simple entre le langage L et le ω-langage lim L reconnu par un automate déterministe: lim L est l'ensemble des mots infinis ayant un nombre infini de préfixes dans L. Un tel ω-langage est dit déterministe. Cependant le pouvoir d'expression des automates non déterministes de Büchi est strictement plus grand que celui des déterministes. En fait, un ω-langage est reconnaissable si et seulement si il s'écrit comme combinaison booléenne de ω-langages déterministes (McNaughton). Il en résulte que pour obtenir l'équivalence entre déterministes et non-déterministes, il faut utiliser la condition d'acceptation de Muller. L'équivalence entre automates finis et expression rationnelles a également été généralisée aux ω-langages. Il faut introduire une itération infinie, notée L → Lω.

Il a fallu huit ans pour atteindre le niveau suivant, qui consistait à étendre le théorème des variétés d'Eilenberg aux ω-langages. Rappelons brièvement les idées principales de cette théorie. Le point de départ est que les semigroupes constituent une contrepartie algébrique des automates qui a l'avantage de ne pas être latéralisée. En particulier, on peut attacher de façon canonique à chaque langage reconnaissable un semigroupe fini, le semigroupe syntactique . L'idée-clé de la théorie des variétés (Eilenberg 1976) est de classer les langages reconnaissables en fonction des propriétés algébriques de leurs semigroupes syntactiques. De façon plus précise, une variété de semigroupes (finis) est une classe de semigroupes fermée par passage au sous-semigroupe, au quotient et au produit direct fini. Le théorème d'Eilenberg donne une correspondance bijective entre les variétés de semigroupes et certaines classes de langages reconnaissables, les variétés de langages. Les variétés de langages sont en particulier fermées par union finie, intersection finie et complément.

S'appuyant sur les travaux d'Arnold, Pécuchet et Perrin, Wilke a obtenu une version d'une théorème d'Eilenberg pour les mots finis et infinis. Le mot "et" est en italiques car il est important de travailler simultanément sur les mots finis et infinis pour avoir une théorie satisfaisante. D'autre part, comme la notion de mot infini est asymétrique, les semigroupes ne suffisent plus. Il faut les remplacer par des ω-semigroupes, qui sont, grosso modo, des semigroupes équipés d'un produit infini. Le bien-fondé de ce point de vue a été confirmée par des travaux récents de Perrin, Pin et Wilke.

L'un des points cruciaux de cette théorie est la relation entre variétés de langages et variétés de ω-langages. En effet, comme l'avait observé Pécuchet, il y a au moins trois façons naturelles d'associer une classe de ω-semigroupes à une variété de semigroupes finisV. On peut considérer les ensembles reconus par un ω-semigroupe fini S dont la partie "semigroupe" appartient à V, ou, par analogie avec le théorème de Kleene, les ensembles reconnus par un automate de Büchi dont le semigroupe de transition appartient à V, ou enfin, inspiré par le théorème de McNaughton, les combinaisons booléennes d'ensembles de la forme lim L où L est reconnu par un semigroupe de V. Malheureusement, ces trois classes sont en général distinctes, et leur étude nécéssite des outils sophistiqués.

L'auteur a proposé en [82] d'introduire un ordre partiel sur le semigroupe syntactique, ce qui conduit à la notion de semigroupe syntactique ordonné. L'extension de la théorie des variétés qui en résulte permet de prendre en compte des classes de langages reconnaissables qui sont fermées par union et intersection, mais pas nécessairement par complément, une différence majeure avec la théorie initiale.

Le but de cet article est d'étendre ces résultats au mots infinis. Comme de coutume, il faut surmonter certaines difficultés techniques, à la fois dans le choix des définitions (cf., par exemple, la définition d'au automate de Büchi non déterministe ordonné) et dans les démonstrations. Mais la théorie se généralise finalement assez bien et fournit en particulier les résultats suivants:
  1. Un nouveau théorème des variétés: il y a une correspondance bijective entre les variétés de ω-semigroupes ordonnés et les variétés positives de ω-langages.

  2. Une caractérisation purement algébrique de certaines classes topologiques de ω-langages reconnaissables: par exemple, on dispose d'une caractérisation de ce type pour les ouverts (appelés également ensembles &Sigma1), les fermés (ou ensembles &Pi1), les ensembles &Pi2 et &Sigma2.

  3. Une caractérisation des ω-langages reconnus par un automate de Büchi ordonné dont le semigroupe de transition ordonné appartient à une variété donnée V : ce sont exactement les unions finies de ω-langages de la forme XYω, où XY* et Y+ sont des V-languages (ce qui étend un résultat de Pécuchet).

  4. Une étude détaillée des différentes classes de ω-langages associées aux idéaux de mélange et aux langages testables par morceaux, une importante classe de langages reconnaissables étudiés par Simon.


Extended Abstract : This paper is a contribution to the theory of languages of infinite words, or ω-languages. This theory has been so far quite successful, in the sense that most known results on languages have been extended to ω-languages, but it does not mean that these generalizations are trivial. The best example is the equivalence between deterministic and non-deterministic finite automata. This result is relatively easy for languages, but becomes really tricky for ω-languages. Indeed, with the acceptance condition introduced by Büchi, there is a simple relation between the language L and the ω-language lim L recognized by a deterministic automaton: lim L is the set of infinite words having infinitely many prefixes in L. Such ω-languages are called deterministic. But non-deterministic Büchi automata are strictly more powerful than deterministic ones. Actually an ω-language is recognizable if and only if it is a boolean combination of deterministic ω-languages (McNaughton). Therefore, Muller's stronger condition of acceptance is required to obtain the equivalence between deterministic and non deterministic automata. The equivalence between automata and rational expressions has been also generalized to ω-languages. It involves an infinite iteration, denoted L → Lω.

It took about eight years to reach the next level, which consisted in generalizing Eilenberg's variety theory to ω-languages. Let us briefly remind the main ideas of this theory. The starting point is the observation that finite semigroups can be viewed as a two-sided algebraic counterpart of finite automata. In particular, a finite semigroup, called the syntactic semigroup, is canonically attached to each recognizable language. The key idea of the variety theory (Eilenberg 1976) is to classify recognizable languages according to the algebraic properties of their syntactic semigroup. More precisely, a variety of (finite) semigroups is a class of finite semigroups closed under the taking of subsemigroups, quotients and finite direct product. Eilenberg's theorem states that varieties of semigroups are in one to one correspondence with certain classes of recognizable languages, the varieties of languages. Varieties of languages are in particular closed under finite union, finite intersection and complement.

Carrying on the work of Arnold, Pécuchet and Perrin, Wilke has obtained a counterpart of Eilenberg's variety theorem for finite and infinite words. The word "and" is emphasized in the last sentence, because it is really important to work simultaneously with finite and infinite words. Furthermore, since the notion of infinite word is asymmetrical, finite semigroups are not suitable any more. They can be replaced by ω-semigroups, which are, roughly speaking, semigroups equipped with an infinite product. The fitness of this approach was corroborated by recent contributions of Perrin, Pin and Wilke.

One of the critical point in this theory is the relationship between varieties of languages and varieties of ω-languages. Indeed, as was observed by Pécuchet, there are at least three natural ways to associate a class of ω-languages to a variety of finite semigroups V. One can consider the sets recognized by a finite ω-semigroup S whose semigroup part belongs to V, or, by analogy with Kleene's theorem, the sets recognized by a Büchi automaton whose transition semigroup belongs to V, or finally, inspired by McNaughton's theorem, the boolean combinations of sets of the form lim L where L is recognized by a semigroup of V. Unfortunately, these three classes are distinct in general, and their study requires some sophisticated tools.

A variant of the notion of syntactic semigroup was recently proposed by the author [82]. The key idea is to define a partial order on syntactic semigroups, leading to the notion of ordered syntactic semigroups. The resulting extension of Eilenberg's variety theory permits to treat classes of languages that are closed under union and intersection, but not necessarily under complement, a major difference with the original theory.

The aim of this paper is to extend these results to infinite words. As usual, there are a few technical difficulties to overcome, both in the basic definitions (see, for instance, the definition of a non-deterministic ordered Büchi automata) and in the proofs. But the theory can be generalized fairly smoothly, and our main results are listed below:
  1. A new variety theorem: there is a one to one correspondence between varieties of ordered ω-semigroups and positive varieties of ω-languages.

  2. A purely algebraic characterization of some topological classes of recognizable ω-languages: for instance the open (also called &Sigma1 sets, the closed (or &Pi1) sets, the &Pi2 and &Sigma2 sets admit such a characterization.

  3. A characterization of the ω-language recognized by an ordered Büchi automaton whose ordered transition semigroup belongs to a given variety V : they are exactly the finite unions of ω-languages of the form XYω, where XY* and Y+ are V-languages. (This extends a result of Pécuchet.)

  4. A detailed study of the different classes of ω-languages that can be associated with shuffle ideals and piecewise testable languages, an important class of recognizable languages studied by Simon.

PostScript file compressed with gzip, PDF file

Valid HTML 4.01!