Bibliothèques d’automates finis et grammaires context-free : de nouveaux traitements informatiques
Matthieu Constant
Résumé : La quantité de documents disponibles via Internet explose. Cette situation nous incite à rechercher de nouveaux outils de localisation d’information dans des documents et, en particulier, à nous pencher sur l’algorithmique des grammaires context-free appliquée à des familles de graphes d’automates finis (strictement finis ou à cycles). Nous envisageons une nouvelle représentation et de nouveaux traitements informatiques sur ces grammaires, afin d’assurer un accès rapide aux données et un stockage peu coûteux en mémoire.
Abstract : The amount of documents available over the Internet is exploding. This phenomenon requires the development of new electronic representations and tools to search information into these documents. This article deals with context-free algorithms applied to finite state graphs (strictly finite or with cycles). It shows new methods and representations to combine efficiently complexities in terms of memory space and processing time.
Mots clés : Automates finis, forme normale de Greibach, grammaires context-free, graphes
Keywords : Context-Free Grammars, Finite State Automata, Graphs, Greibach Normal Form