Résumé : Le résultat principal de cet article
affirme qu'un langage reconnaissable est ouvert dans la topologie de Hall
si et seulement si il appartient à la fermeture polynomiale
PolG des langages à groupe. Un langage à groupe est
un langage reconnaissable reconnu par un automate de permutations. La
fermeture polynomiale d'une classe de langages C est l'ensemble des
langages qui sont unions finies de langages de la forme
L0a1L1...
anLn, where the ai, où
les ai sont des lettres et les Li sont
des éléments de C. La topologie de Hall est la
topologie dans laquelle les ouverts sont union (finie ou infinie) de
langages à groupe. On donne aussi une description combinatoire de
ces langages ainsi qu'une caractérisation syntacticque. Soit
L un langage reconnaissable de A*, soit M son
monoïde syntactique et soit P son image syntactique. Alors
L appartient à PolG si et seulement si, pour tout
s,t dans M et pour tout idempotent e de M,
st dans P entraine set dans P. Finalement, on
donne une caractérisation sur l'automate minimal de L qui
conduit à un algorithme en temps polynomial pour tester,
étant donné un automate fini deterministe, s'il
reconnaît un langage de PolG.
Abstract : This main result of this paper states that a recognizable
language is open in the Hall topology if and only if it belongs to the
polynomial closure PolG of the group languages. A group language is
a recognizable language accepted by a permutation automaton. The
polynomial closure of a class of languages C is the set of languages
that are finite unions of languages of the form
L0a1L1...
anLn, where the ai's are
letters and the Li's are elements of C. The Hall
topology is the topology in which the open sets are finite or infinite
unions of group languages. We also give a combinatorial description of
these languages and a syntactic characterization. Let L be a
recognizable set of A*, let M be its syntactic
monoid and let P be its syntactic image. Then L belongs to
PolG if and only if, for every s,t in M and for every
idempotent e of M, st in P implies set
in P. Finally, we give a characterization on the minimal automaton
of L that leads to a polynomial time algorithm to check, given a
finite deterministic automaton, whether it recognizes a language of
PolG.