Dépôt institutionnel de l'UQO
RECHERCHER

Équivalence des grammaires de fonction simple

Bastien, Cédric (2006). Équivalence des grammaires de fonction simple. Mémoire. Gatineau, Université du Québec en Outaouais, Département d'informatique et d'ingénierie, 63 p.

Le plein texte n'est pas disponible pour ce document.

Résumé

Une grammaire simple est une grammaire LL(1) en forme normale de Greibach. Si l’alphabet d’une grammaire simple est l’union de deux alphabets, un alphabet d’entrée ∑ et un alphabet de sortie Ω, la grammaire est une grammaire de fonction simple. Une fonction simple est une application partielle F : ∑* → Ω* définie à partir d’un symbole non-terminal d’une grammaire de fonction simple. Étant donnés deux non-terminaux A et B d’une grammaire de fonction simple, le problème d’équivalence des grammaires de fonction simple consiste à déterminer si les fonctions simples définies par A et B sont les mêmes. Les fonctions simples sont utilisées pour une technologie de classification de paquets sur les réseaux pour représenter efficacement les règles de classification. Comme la taille des règles peut être considérable, il importe de pouvoir identifier les facteurs qui sont communs à plusieurs règles afin d’éviter de les dupliquer inutilement. Cette tâche nécessite l’utilisation d’un algorithme d’équivalence des grammaires de fonction simple. Nous présentons dans ce mémoire un algorithme permettant de résoudre efficacement le problème d’équivalence des grammaires de fonction simple. Cet algorithme fonctionne en temps polynomial par rapport à n, la taille de la description de la grammaire d’entrée, et || G||, la longueur maximale d’un mot le plus court pouvant être engendré par un non-terminal de la grammaire. C’est le premier algorithme permettant de résoudre ce problème. Nous présentons également un algorithme permettant de résoudre le problème d’équivalence des grammaires simples. Cet algorithme fonctionne en temps O(n7log²n), où n est la taille de la description de la grammaire d’entrée, améliorant la borne supérieure précédente qui était O(n13). Nous présentons finalement une étude comparant les performances pratiques de notre algorithme d’équivalence des grammaires simples avec celles des deux principaux algorithmes déjà existants pour résoudre ce problème.

Type de document: Thèse (Mémoire)
Directeur de mémoire/thèse: Czyzowicz, Jurek
Co-directeurs de mémoire/thèse: Fraczak, Wokciech
Informations complémentaires: Bibliothèque L.-Brault QA 76 .9 A43 B37 2006 Comprend des réf. bibliogr. : p. [61]-63
Mots-clés libres: Algorithmes; Langages de programmation
Départements et école, unités de recherche et services: Informatique et ingénierie
Date de dépôt: 10 déc. 2012 21:18
Dernière modification: 01 août 2013 15:10
URI: http://di.uqo.ca/id/eprint/285

Actions (Identification requise)

Dernière vérification avant le dépôt Dernière vérification avant le dépôt