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 28 Mai 2013

Le problème de finitude des semi-groupes d'automates

par Pierre Gillibert (LIAFA, Paris)

Une machine de Mealy (transducteur fini lettre à lettre déterministe), permet de définir un semi-groupe, engendré par les applications sur les mots induites par l'automate. La question suivante est beaucoup étudié :

Quelque résultats positifs sont connus, cependant le problème dans le cas général est indécidable. La preuve est basée sur les pavages de Wang NW-déterministes.

Plus précisément, étant donné un pavage de Wang déterministes, on peut construire un automate de Mealy, tel que le pavage permet de paver le plan si et seulement si l'automate de Mealy engendre un semi-groupe fini.

La construction est basée sur une construction de Kari, utilisée pour prouver que le problème de nilpotence des automates cellulaires est indécidable. En effet Kari montre aussi que le problème de pavage du plan est indécidable dans le cas NW-déterministe. En conséquence le problème de finitude des groupes d'automates est indécidable.

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