Séminaire Gaston Darboux :

Le 07 avril 2017 à 11:15 - salle 430

Présentée par Godin Thibault - Univ. Paris Diderot

Mealy automata: dynamic of the action, singular points and Wang tilings

Mealy automata are a powerful tool to generate (semi)groups. Since the 80's, they have been used to solved several major conjectures in (semi)group theory. Although, people started to study them in a (theoretical) computer science perspective only recently. This approach is rich and brought many interesting results and questions. In this talk, we focus on the dynamic of the action of the group on the regular tree and we show that classical tool from automata theory can be used to simplify and generalize known results and to provide information on this action. Then, we study a closely related problem and use a connection between Mealy automata and Wang tilings to obtain an undecidability theorem. this is based on a joint work with D. D'Angeli, I. Klimann, M. Picantin, and E. Rodaro.