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é :

  • Peut-on décider si un automate de Mealy engendre un semi-groupe fini ?

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.