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 12 Septembre 2017 à 10:30-12:15

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

par Théo Grente (GREYC, Caen)

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.

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