Patrick Dehornoy

Trois problèmes de terminaison

24 octobre 2013

Résumé: On présentera trois problèmes de terminaison provenant de diverses parties de l'algèbre, à savoir celui de l'algorithme polonais pour la loi d'autodistributivité, où la terminaison n'est pas encore démontrée, celui de de la réduction des poignées des tresses, où la terminaison est démontrée mais avec une borne de complexité très grossière, et celui du retournement de sous-mot en théorie des semigroupes, où la terminaison est démontrée dans certains cas particuliers. Dans les trois contextes, les résultats partiels connus reposent sur des propriétés spécifiques des objets mis en jeu, et il serait très intéressant de savoir si des outils plus généraux pourraient permettre d'améliorer ce qu'on sait.