Events

3 December 2008

Mercredi 3 décembre, 11h,
Batiment I, 1er étage,
Centre Commun INRIA-MSR

Modélisation et simulation d’automates à l’aide de machines d’Eilenberg.
Benoit Razet
INRIA Rocquencourt

Un algorithme de reconnaissance pour la langue naturelle est parfois composé d’une variété d’automates (finis, à pile, transducteurs, etc). C’est le cas, par exemple, de la librairie Zen utilisée pour l’analyse syntaxique du sanskrit. Nos recherches visent à abstraire la description de tels algorithmes. Pour cela nous utilisons un modèle de calcul introduit par Samuel Eilenberg. Les machines d’Eilenberg ont, outre la capacité à décrire l’ensemble des automates qui pourraient composer l’algorithme de reconnaissance, une propriété fondamentale de modularité. Nous présenterons le principe de simulation de ces machines à l’aide d’un moteur réactif. Cette technique a l’avantage de pouvoir être spécifiée formellement dans un assistant de preuves comme il a déjà été montré pour la classe particulière des machines d’Eilenberg finies.

Travail en commun avec Gérard Huet.