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

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.