Automates modulaires - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2005

Automates modulaires

Benoit Razet
  • Fonction : Auteur
  • PersonId : 833443

Résumé

L'algorithme de Berry-Sethi pour la compilation des expressions régulières en automates est efficace et présenté de manière élégante. Ce rapport fournit une implémentation de cette technique de compilation dans le langage de programmation PidginML avec l'innovation de compiler des expressions régulières que nous avons étendues. Son élégance tient dans son style de programmation purement fonctionnel et son respect de la complexité théorique de l'algorithme. La propriété de localité des automates obtenus est à la base de la modularité d'automates dans la boîte à outils de linguistique computationnelle Zen2. Ce rapport comporte également une justification formelle de la bonne formation des automates compilés, par un développement dans l'assistant de preuves Coq. Il discute également de l'adaptation de la boîte à outils Zen2 au problème classique de recherche de chaînes de caractères dans un texte (commande grep Unix)

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-5788.pdf (332.09 Ko) Télécharger le fichier

Dates et versions

inria-00070233 , version 1 (19-05-2006)

Identifiants

  • HAL Id : inria-00070233 , version 1

Citer

Benoit Razet. Automates modulaires. [Rapport de recherche] RR-5788, INRIA. 2005, pp.43. ⟨inria-00070233⟩
125 Consultations
221 Téléchargements

Partager

Gmail Facebook X LinkedIn More