MP1/MP*: Option Informatique
DS spécial: langages bidimensionnels



Présentation

Depuis plusieurs années, on cherche à étendre en dimension deux, voire au-delà, les résultats acquis sur les langages de mots (objets de dimension un); le premier travail consiste à définir la notion de mot bidimensionnel; on peut ensuite étudier la complexité d'un tel mot, la reconnaissabilité d'un langage, chercher des classes intéressantes de langages.

La notion de langage reconnaissable peut être définie de plusieurs façons différentes, comme c'était déjà le cas pour les langages de mots ordinaires: automates capables de se déplacer dans les quatre directions (Blum et Hewitt, 1967); automates de tesselation (Inoue et Nakamura, 1977).

Giammarresi et Restivo ont présenté en 1992 une notion de reconnaissabilité inspirée à la fois par les langages locaux et certains types de pavages. Nous allons voir que plusieurs des propriétés des langages reconnaissables unidimensionnels restent valides dans ce cadre.

La version initiale de ce texte a été rédigée par Philippe Espéret.