Automates reconnaissant le langage des mots réduits d'un groupe de Coxeter

Ouimet, Sébastien (2016). « Automates reconnaissant le langage des mots réduits d'un groupe de Coxeter » Mémoire. Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en mathématiques.

Fichier(s) associé(s) à ce document :
[img]
Prévisualisation
PDF
Télécharger (7MB)

Résumé

Dans ce mémoire, nous étudions les automates finis et déterministes reconnaissant le langage Red(W,S) des mots réduits d'un système de Coxeter (W,S). La construction d'automates reconnaissant ce langage est un sujet bien connu depuis plusieurs années : Brink et Howlett (Brink et Howlett, 1993) construisent le premier tel automate en démontrant que les groupes de Coxeter sont automatiques. La technologie des petites racines utilisée par Brink et Howlett est reprise par Eriksson (Eriksson, 1994) pour définir l'automate canonique. En 2015, Hohlweg, Nadeau et Williams (Hohlweg et al., 2015) introduisent une définition simple d'un automate à partir de la notion d'ombre de Garside. Une question est toujours sans réponse : peut-on trouver une construction de l'automate minimal reconnaissant Red(W,S) qui utilise les notions de petites racines ou d'ombres de Garside? Cette question motive le propos de ce mémoire. Après un premier chapitre présentant les groupes de Coxeter, les petites racines et les ombres de Garside, nous définissons, dans le chapitre suivant, l'automate n-canonique en utilisant une généralisation de la technologie des petites racines et des petits ensembles d'inversions de Brink et Howlett. Nous montrons dans quels cas l'automate 0-canonique est minimal. La minimalité de l'automate 0-canonique n'est toutefois pas vérifiée en général et le contre-exemple du groupe de type C2 illustre ce propos. Dans le troisième chapitre, nous discutons de résultats plus récents en introduisant l'automate lié à une ombre de Garside. Nous énonçons une conjecture de Hohlweg, Nadeau et Williams sur la minimalité de l'automate Auts(W,S) lié à la plus petite ombre de Garside. Pour conclure, nous discutons, dans le dernier chapitre de ce mémoire, de problèmes ouverts motivant la minimalité de Auts(W,S) et de la structure automatique des systèmes de Coxeter. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : groupes de Coxeter, automates, automate minimal, mots réduits, racines, petites racines, ordre faible, ombres de Garside, éléments bas, automates multiplicateurs.

Type: Mémoire accepté
Informations complémentaires: Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse: Hohlweg, Christophe
Mots-clés ou Sujets: Groupes de Coxeter / Théorie des automates / Problèmes des mots (Mathématiques) / Ombres de Garside
Unité d'appartenance: Faculté des sciences > Département de mathématiques
Déposé par: Service des bibliothèques
Date de dépôt: 17 nov. 2016 19:59
Dernière modification: 17 nov. 2016 19:59
Adresse URL : http://www.archipel.uqam.ca/id/eprint/9092

Statistiques

Voir les statistiques sur cinq ans...