An explicit formula for the intersection of two polynomials of regular languagesReportar como inadecuado




An explicit formula for the intersection of two polynomials of regular languages - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications

Abstract : Let L be a set of regular languages of A *. An L-polynomial is a finite union of products of the form L0a1L1 · · · anLn, where each ai is a letter of A and each Li is a language of L. We give an explicit formula for computing the intersection of two L-polynomials. Contrary to Arfi-s formula 1991 for the same purpose, our formula does not use comple-mentation and only requires union, intersection and quotients. Our result also implies that if 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.

Résumé : Soit  un ensemble de langages rationnels de *A. Un L-polynôme est une union finie de produits de la forme L0a1L1⋯anLn, où chaque ai est une lettre de A et chaque Li est un langage de . Nous donnons une formule explicite pour calculer l-intersection de deux -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  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.

Keywords : Regular language intersection polynomial closure





Autor: Jean-Eric Pin -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados