An explicit formula for the intersection of two polynomials of regular languages

J.-E. Pin



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.

PDF file

Valid HTML 4.01!