Complexité palindromique des mots et des arbres

Lafrenière, Nadia (2016). « Complexité palindromique des mots et des arbres » 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 (8MB)

Résumé

Ce mémoire concerne l'étude des palindromes, soit les mots qui se lisent de la même façon de gauche à droite et de droite à gauche. On s'intéresse au nombre de facteurs palindromes d'un mot, c'est-à-dire de suites contiguës de lettres qui sont des palindromes. On élargit la portée de théorèmes connus aux σ-palindromes, une variante qui permet de considérer des transformations différentes de l'image miroir. On choisit alors σ comme une permutation involutive des lettres de l'alphabet et un σ-palindrome est un point fixe de la composition du miroir et de σ. On expose des algorithmes permettant de calculer le nombre de σ-palindromes et le σ-défaut, une mesure de densité en σ-palindromes originaux. On établit aussi une relation entre le σ-défaut et le nombre de facteurs et de σ-palindromes de chaque longueur, qui s'applique tant aux mots finis qu'aux mots infinis qui sont aussi périodiques, fermés par la composition de σ et de l'opérateur miroir, uniformément récurrents ou points fixes de morphismes primitifs. On considère ensuite des arbres finis dont les arêtes sont étiquetées par des lettres. La trace d'un chemin de l'arbre définit un mot qui appartient au langage de l'arbre. On se penche sur le nombre maximal de palindromes que peut contenir un tel arbre. On remarque alors que ce nombre est plus grand que l'analogue pour les mots. On fournit enfin une borne asymptotique du nombre de palindromes dans les arbres ayant une certaine structure et on survole la résolution du problème général, récemment découverte. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Combinatoire des mots, palindromes, complexité palindromique, pseudopalindromes, défaut palindromique, arbres.

Type: Mémoire accepté
Informations complémentaires: Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse: Brlek, Srecko
Mots-clés ou Sujets: Combinatoire des mots / Palindromes / Arbres (Théorie des graphes)
Unité d'appartenance: Faculté des sciences > Département de mathématiques
Déposé par: Service des bibliothèques
Date de dépôt: 22 juin 2016 13:54
Dernière modification: 22 juin 2016 13:54
Adresse URL : http://archipel.uqam.ca/id/eprint/8647

Statistiques

Voir les statistiques sur cinq ans...