Résumé : Soit \(\mathcal{L}\) un ensemble de langages
rationnels de \(A^*\). Un
\(\mathcal{L}\)-polynôme est une union finie de produits de la forme \(L_0 a_1
L_1 \dotsm a_n L_n\), où chaque \(a_i\) est une lettre de \(A\) et chaque
\(L_i\) est un langage de \(\mathcal{L}\). Nous donnons une formule
explicite pour calculer l'intersection de deux
\(\mathcal{L}\)-polynômes. Contrairement à la formule utilisée par Arfi
(1991) pour le même calcul, notre formule n'utilise pas la
complémentation et nécessite seulement l'union, l'intersection et les quotients.
Ce résultat montre aussi que si \(\mathcal{L}\) est fermé par union,
intersection et quotient, alors sa fermeture polynomiale, sa fermeture polynomiale
non ambigüe et sa fermeture polynomiale deterministe à gauche [droite]
sont également fermées pour ces opérations.
Abstract :
Let \(\mathcal{L}\) be a set of regular languages of \(A^*\). An
\(\mathcal{L}\)-polynomial is a finite union of products of the form \(L_0 a_1
L_1 \dotsm a_n L_n\), where each \(a_i\) is a letter of \(A\) and each
\(L_i\) is a language of \(\mathcal{L}\). We give an explicit formula for
computing the intersection of two \(\mathcal{L}\)-polynomials. Contrary to
Arfi's formula (1991) for the same purpose, our formula does not use
complementation and only requires union, intersection and quotients.
Our result also implies that if \(\mathcal{L}\) is closed under union,
intersection and quotient, then its polynomial closure, its
unambiguous polynomial closure and its left [right] deterministic
polynomial closure are closed under the same operations.