Résumé : La fermeture polynomiale d'une classe de
languages C est l'ensemble des langages qui peuvent
s'écrire comme union finie de langages de la forme
L0a1L1...
anLn, où les ai sont des
lettres et les Li sont des éléments de
C.
Le résultat principal de cet article est une description
équationnelle de la fermeture polynomiale d'une classe de langages
C à partir d'une description équationnelle de
C, lorsque C est un treillis de langages
fermé par quotients. Comme application de ce résultat, nous
donnons un ensemble d'équations définissant la fermeture
polynomiale des langages de la forme u* ou
A*, où u est un mot, et nous utilisons ces
équations pour montrer que cette classe est décidable.
Abstract : 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 main result of this paper gives an equational description of the
polynomial closure of C, given an equational description of
C, when C is a lattice of regular languages
closed under quotients. As an application of this result, we give a set of
equations defining the polynomial closure of the languages of the form
u* or A*, where u is a word, and
we use these equations to show that this class is decidable.