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 27 Septembre 2016

Quelques liens entre les automates trellis et les langages algébriques

par Véronique Terrier (GREYC, Caen)

Cet exposé présente un modèle très simple de calcul, les automates trellis. Malgré sa simplicité, ce modèle contient les caractéristiques essentielles du calcul massivement parallèle et, de ce fait, déterminer ses capacités et ses limites est un enjeu significatif.

Une approche classique pour déterminer le pouvoir d'expressivité d'un modèle est de comparer ses performances avec celles d’autres modèles. Dans cet exposé, on s'intéressera aux relations entre ces automates trellis et les grammaires algébriques. En effet, ce type d'automate et les grammaires algébriques sont à la fois proches (tous les deux peu gourmands en terme de ressources) et incomparables (dans leur mécanismes et les classes de langages qu'ils caractérisent).

On verra en particulier que les langages algébriques peu denses (ceux dont le nombre de mots pour chaque longueur est borné polynomialement) sont reconnus par les automates trellis.

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