Problèmes algorithmiques dans les groupes de tresses
Institution:
Rennes 1Disciplines:
Directors:
Abstract EN:
The aim of this thesis is to develop new algorithms for the braid groups. An important problem in the mathematical theory of braids is to improve the existing algorithms to solve the conjugacy problem. We completely solve this problem in the case of the 4-strand braid group, by developing an algorithm of cubic complexity in term of the length of the input. The demonstration leans on two fundamental aspects of braid groups: the structure of Garside group and the structure of Mapping Class Group. As a preliminary result, we develop an algorithm of quadratic complexity which classifies 4-strand braids according to their Nielsen-Thurston type. More generally, we study this problem of classification for an arbitrary number of strands. We give an adaptation of known results by Benardete-Gutiérrez-Nitecki in the frame of the dual Garside structure. Finally, with the help of a deep (non-constructive) result by Masur and Minsky, we show the existence of a polynomial time algorithm for deciding the Nielsen-Thurston type of agiven braid with arbitrarily many strands.
Abstract FR:
Cette thèse a pour objet de développer de nouveaux algorithmes pour les groupes de tresses. Un problème important en théorie mathématique des tresses est d'améliorer les algorithmes existants pour résoudre le problème de conjugaison. Nous résolvons complètement ce problème dans le cas du groupe des tresses 4 brins, en exhibant un algorithme de complexité cubique en terme de la longueur des entrées. La démonstration s'appuie sur deux aspects fondamentaux des groupes de tresses : la structure de groupe de Garside et la structure de groupe de difféotopie. Comme résultat préliminaire, nous développons un algorithme de complexité quadratique capable de classifier les tresses 4 brins selon leur type de Nielsen-Thurston. Plus généralement, nous étudions ce problème de classification pour un nombre arbitraire de brins. Nous donnons une adaptation des résultats connus de Benardete-Gutiérrez-Nitecki au cadre de la structure de Garside duale. Enfin, à l'aide d'un résultat profond (et non-constructif) de Masur et Minsky, nous prouvons l'existence d'un algorithme de complexité polynômiale pour décider le type de Nielsen-Thurston d'une tresse avec un nombre de brins arbitraire.