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:
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.
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.
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).
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:
A new variety theorem: there is a one to one correspondence
between varieties of ordered ω-semigroups and positive varieties of
ω-languages.
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.
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.)
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