Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 17 Novembre 2009

Les Xor-automates, une forme normale compacte pour les langages réguliers

par Nicolas Gama (GREYC, Caen)

La seule forme normale connue pour un langage régulier L est son automate deterministe minimal MDA(L). Nous montrons qu'un langage régulier est aussi caractérisé par une dimension finie dim(L), qui est toujours plus petite (voire exponentiellement plus petite) que le nombre d'états |MDA(L)| de l'automate minimal. Cette dimension est le nombre minimal d'états des xor-automates non-deterministes (NXA) qui acceptent le langage. Les NXAs combinent les avantages des automates déterministes (l'existence de forme normale, compatibilité avec la négation, algorithmes de minimisation, notion d'équivalence d'états et d'accessibilité) et les avantages des automates non déterministes (représentation compacte, ou matricielle, compatibilité avec le miroir). Nous donnons un algorithme de minimisation qui produit en temps cubique le xor-automate minimal de L: MXA(L) à partir de n'importe quel NXA reconnaissant L. Le MXA est une forme normale du langage L=L'<=>MXA(L)=MXA(L'). La manière dont notre algorithme fonctionne permet d'établir un lien entre l'algorithme de Brzozowski (qui minimise un automate deterministe en utilisant le langage miroir) et les autres algorithmes basés sur l'équivalence d'états (quotient de Nerode, ou autres).

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr