Comparaison des langages d’Okhotin avec les classes de complexité des automates cellulaires

Afin d’étudier la pertinence d’une classe de problèmes (classe caractérisée par la complexité à décrire ces problèmes) donnée dans un domaine comme la théorie des langages ou la logique, on cherche à comparer celle-ci à une complexité calculatoire. En théorie des langages, plusieurs équivalences ont déjà été déterminées : les langages réguliers sont exactement ceux reconnaissables par un automate fini, les langages algébriques exactement ceux reconnaissables par automate à pile non déterministe.

Alexander Okhotin a quant à lui montré que les langages linéaires conjonctifs sont équivalents aux langages reconnus par automate treillis (automate cellulaire à voisinage unidirectionnel). L’objectif de ce stage est d’étudier les autres familles de langages définies par A. Okhotin par le prisme de leur reconnaissance par un automate cellulaire.