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 :
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://archipel.uqam.ca/id/eprint/9092 |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
