UQAM - Université du Québec à Montréal
Archive de publications électroniques
UQAM ›  Archive de publications électroniques ›  Propriétés combinatoires des f-palindromes

Propriétés combinatoires des f-palindromes

Labbé, Sébastien (2008). « Propriétés combinatoires des f-palindromes » 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
2444Kb

Résumé

Ce mémoire fait partie du domaine de la combinatoire des mots et plus particulièrement de l'étude de la complexité palindromique (le nombre de facteurs palindromes) des mots infinis. La conjecture de Hof, Knill et Simon, énoncée pour la première fois en 1995, donne une caractérisation des points fixes dont la complexité palindromique est infinie. Récemment, elle a été résolue pour les points fixes sur un alphabet binaire (Tan, 2007). Dans ce mémoire, nous la démontrons pour les points fixes de morphismes uniformes sur un alphabet binaire (ce n'est pas plus général que le résultat de Tan). De plus, notre approche permet d'obtenir une démonstration d'un résultat similaire pour les points fixes contenant une infinité d'antipalindromes. Afin d'atteindre notre objectif, nous établissons un ensemble de résultats combinatoires sur les mots. En effet, nous faisons une étude des ƒ-palindromes et de certaines équations qui en contiennent. Ensuite, nous introduisons les morphismes de classe P, P¹ et ƒ-P et nous démontrons notamment que l'ensemble des morphismes de classe P¹ est un monoïde. Nous rassemblons également les résultats d'un travail précédent sur les morphismes conjugués. Finalement, nous étudions les chevauchements de mots et nous construisons un graphe de chevauchements, assise de notre démonstration de la conjecture. Toutes ces recherches ont contribué au développement d'un outil informatique voué à l'étude de questions soulevées en combinatoire des mots. Ce dernier est constitué d'un ensemble de classes et de fonctions écrites en langage Python annexées à ce mémoire. Elles seront bientôt incluses dans un paquetage sur la combinatoire des mots associé au logiciel libre Sage. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Combinatoire des mots, ƒ-palindrome, Complexité palindromique, Conjecture de Hof, Knill et Simon, Point fixe de morphisme, Chevauchement, Automates.

Type de document : Mémoire accepté
Directeur de thèse : Brlek, Srecko
Évaluation par des pairs : Oui
État du document : Non publié
Informations complémentaires : Le mémoire a été numérisé tel que transmis par l'auteur.
Mots-clés : Combinatoire des mots, Morphisme (Mathématiques), Palindrome, Automate
Unité d'appartenance : Faculté des sciences > Département de mathématiques
Code ID : 1534
Déposé par : RB Service des bibliothèques
Déposé le : 23 déc. 2008
Dernière modification : 13 déc. 2010 10:48

Modifier les métadonnées de ce document.

Voir les statistiques sur cinq ans...