Evènement pour le groupe Séminaire Méthodes Formelles


Date 2020-05-05  14:00-15:00
TitreOrder problem for automaton semigroups  
RésuméThe class of automaton (semi)groups--that is (semi)groups generated by functions defined using transducers--has been studied since the late 70's as many very interesting (semi)groups arise from it. From a computer scientist point of view it is also very nice because the underlying automaton structure allows to apply known tools, and for instance one can decide if an element represents the identity element using automaton minimization. In this talk, we focus on a the order problem, that is given an element g in the (semi)group, does there exist two distinct integers l,m such that g^l=g^m ? This problem was proven undecidable for general automaton (semi)groups by Gilibert, but Bondarenko, Bondarenko, Sidki and Zapata showed that, if one restricts the automaton, then the problem is decidable in the group case. We extend their result to the semigroup case, introducing several extensions of their work. This is joint work with Laurent Bartholdi, Ines Klimann and Matthieu Picantin  
LieuTBA 
OrateurThibault Godin  
Emailhttps://www.irif.fr/~godin/ 
UrlUniversité de Montpellier, Université de Lorraine 



Aucun document lié à cet événement.

Retour
Retour à l'index