Blanchette, Benjamin
(2019).
« Des groupes automatiques aux semigroupes quasi-automatiques » Mémoire.
Montréal (Québec), Université du Québec à Montréal, Maîtrise en mathématiques.
Fichier(s) associé(s) à ce document :
Résumé
Ce mémoire cherche à exposer les différentes classes de semigroupes, monoïdes et groupes définies en fonction de leur complexité de calcul. On y présente les relations connues entre ces classes ainsi que plusieurs résultats relatifs à des problèmes fondamentaux pour ces structures. Dans le premier chapitre, on introduit les notions algébriques préalables à l'étude de ces objets. La notion classique de partie rationnelle d'un monoïde est critique. Nos travaux utilisent beaucoup les machines abstraites, avec comme prototype l'automate. On présente et utilise aussi les transducteurs, les automates miroir et les automates à deux bandes. Une notion fondamentale particulière à notre sujet est la notion de dictionnaire: un ensemble rationnel de représentants d'une structure algébrique. Les relations multiplicatives élémentaires d'un dictionnaire et leurs caractéristiques comme parties du monoïde produit A* x A* forment notre principal outil dans l'étude de la complexité calculatoire des structures. Dans le deuxième chapitre, on établit les relations connues entre les diverses classes. Essentiellement, on démontre que les structures automatiques sont asynchrones, qui elles sont quasi-automatiques, et on caractérise géométriquement ces classes avec les propriétées Lipschitz. On démontre aussi que les notions de groupes et monoïdes automatiques ne dépendent pas du choix de système d'écriture. On introduit aussi notre nouvelle classe, les semigroupes quasi-automatiques, et on établit les relations avec les autres classes présentées précédemment. On montre aussi que cette notion ne dépend pas du choix de système d'écriture. Dans le troisième et dernier chapitre, on présente des théorèmes assurant la décidabilité de plusieurs problèmes computationnels pour les semigroupes quasi-automatiques et automatiques. On montre que le problème du mot est résoluble en temps exponentiel pour les semigroupes quasi-automatiques et en temps quadratique pour les semigroupes automatiques. On montre qu'il est décidable de déterminer si un monoïde quasi-automatique est un groupe. Finalement, on montre qu'il existe une inégalité isopérimétrique exponentielle pour les groupes quasi-automatiques et quadratique pour les groupes automatiques.
_____________________________________________________________________________
MOTS-CLÉS DE L’AUTEUR : Groupes automatiques, semigroupes quasi-automatiques, complexité algorithmique, théorie des semigroupes, théorie des automates, théorie des langages formels, combinatoire, algèbre abstraite
| Type: |
Mémoire accepté
|
| Informations complémentaires: |
Fichier numérique reçu et enrichi en format PDF/A. |
|
Directeur de thèse: |
Reutenauer, Christophe |
| Mots-clés ou Sujets: |
Théorie des groupes / Semi-groupes / Complexité de calcul / Théorie des automates / Langages formels / Combinatoire / Algèbre abstraite |
| Unité d'appartenance: |
Faculté des sciences > Département de mathématiques |
| Déposé par: |
Service des bibliothèques
|
| Date de dépôt: |
05 nov. 2025 15:23 |
| Dernière modification: |
05 nov. 2025 15:23 |
| Adresse URL : |
http://archipel.uqam.ca/id/eprint/18882 |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
