Travaux Pratiques: Combinatoire des Mots

Note

Indications de difficulté des exercices

(*) Requiers un peu de programmation (fonctions, ...)

(**) Plus difficile

(projet)

Historique

Début 1906

Morse (1920-1930): systèmes dynamiques

Gros développements: 1960

  • École Française (Schützenberger)
  • École Russe

Mots finis

Exercice: Mots finis

  1. Construire le mot “adacbdafea”:

    sage: # edit here
    

    Indication: Consulter la documentation de la fonction Word(), ainsi que Demonstration: Combinatorics on words

  2. Explorer ses propriétés (est-il un palindrome?):

    sage: # edit here
    

    Indication: utiliser la complétion automatique

Exercice: Décimales de \(\pi\)

  1. Construire le mot constitué des \(100\) premières décimales de \(pi\):

    sage: # edit here
    

    Indications: numerical_approx() et la méthode str.

  2. Compter ses facteurs de longueur \(2\):

    sage: # edit here
    
  3. Combien de décimales de \(\pi\) faut-il pour trouver tous les mots de longueur \(1\), \(2\), \(3\), ... comme facteurs?

    sage: # edit here
    
  4. Comparer avec un mot aléatoire:

    sage: # edit here
    

Exercice: Ensemble des mots

  1. Lister tous les mots de longueur 6 sur l’alphabet “abc”:

    sage: # edit here
    

    Indication: Words()

  2. Lister tous les mots primitif de longueur \(6\):

    sage: # edit here
    

    Indication: Tutorial: Comprehensions, Iterators, and Iterables.

  3. Trouver le plus petit mot tel que (.. TODO:: trouver une bonne propriété)

Langages, codes et Morphismes

Définition

Un langage \(X\) est un sous ensemble de \(A^*\)

Codes

Définition

Un langage \(X\) est un code si tout mot \(w\in A^*\) admet au plus une factorisation sur \(X\).

Exemple

\(X = \{a,ba\}\)

Exemple: codes préfixes

\(X\) est un code préfixe si \(x\in X\) préfixe de \(y\) implique que \(x=y\)

Exercice

  1. Factoriser le mot \(aaaababaaba\) sur le code \(X=\{a,ba\}\):

    sage: # edit here
    
  2. (*) Implanter une fonction factor_a_ba(w) qui renvoie la factorisation d’un mot sur le code \(X=\{a,ba\}\):

    sage: # edit here
    
  3. (*) Implanter une fonction factor_prefixe(w,X) qui renvoie la factorisation d’un mot sur un code préfixe:

    sage: # edit here
    
  4. (**) Implanter une fonction factor(w, X) qui renvoie la factorisation d’un mot \(w\) sur un code \(X\) quelconque:

    sage: # edit here
    
  5. Déterminer la complexité des algorithmes sous-jacents.

Exercice

  1. (*) Implanter une fonction est_code_prefixe(X) qui teste si un langage fini \(X\) est un code préfixe:

    sage: # edit here
    
  2. (projet) Intégrer dans Sage des fonctionnalités autour de la factorisation sur les codes? Ou vaut-il mieux attendre que l’on ait des automates?

Morphismes

Définition

\(f:A^*\mapsto B^*\) est un morphisme si \(f(uv)=f(u)f(v)\)

Exercice

Montrer que \(f(\epsilon) = \epsilon\).

Indication: on pourra utiliser que \(A^*\) est simplifiable à gauche et à droite: si \(ux=uy\) ou \(xu=yu\), alors \(x=y\).

Exercice

Construire dans Sage les morphismes:

  1. \(f: a\mapsto aba, b\mapsto cb, c\mapsto aba\):

    sage: # edit here
    
  2. \(g: a\mapsto ab, b\mapsto ba, c\mapsto a\):

    sage: # edit here
    

Indication: consulter la documentation de WordMorphism()

Quelle est l’image de “acbccacbacaabcab” par ces morphismes?

sage: # edit here

Exercice: puissances itérées

  1. Construire un mot et un morphisme de votre choix:

    sage: # edit here
    
  2. Quelle est la longueur de \(f^{10}(w)\)?

    sage: # edit here
    
  3. Tracer la courbe de la fonction \(n\mapsto l(n)\)\(l(n)\) est la longueur de \(f^n(w)\):

    sage: # edit here
    
  4. Remarquer que la longueur de \(f^n(w)\) ne dépend pas de l’ordre des lettres de \(w\). Utiliser ce fait pour ramener le calcul de la longueur de \(f^n(w)\) au calcul d’une puissance de matrice (abélianisation):

    sage: # edit here
    

    Évaluer la complexité du calcul de \(l(n)\) par cet algorithme.

  5. Utiliser ce fait pour retracer la courbe en échelle logarithmique pour \(n\) aussi grand que possible:

    sage: # edit here
    
  6. Explorer d’autres mots et d’autres morphismes et étudier comment la complexité évolue:

    sage: # edit here
    

Proposition

Un morphisme \(f: A^*\mapsto B\) est injectif si et seulement si:

  1. \(f\) restreint à l’alphabet \(A\) est injectif
  2. \(f(A)\) est un code

Exercice

  1. (*) Implanter une fonction est_injective(f) qui calcule si le morphisme \(f\) est injectif:

    sage: # edit here
    
  2. (*) Implanter une fonction preimage(f,w) qui calcule la préimage d’un mot \(f\) par une fonction \(f\) injective:

    sage: # edit here
    
  3. (projet) Intégrer ces méthodes dans Sage

Théorème du défaut

Deux formulations:

  1. Soit \(X\subset A^*\) fini. Si \(X\) n’est pas un code, alors il existe \(Y\subset A^*\) tel que \(|Y|<|X|\) et tout mot de \(X\) se factorise sur \(Y\).

    Par récurrence, on peut supposer sans perte de généralité que \(Y\) est un code.

  2. Soit \(f: A^* dans B^*\) un morphisme, alors il existe un alphabet \(A'\), \(g:A'^*\mapsto B^*\) et \(g:A^*\mapsto A'^*\) tel que \(|A'|<|A|\) et \(f=g\circ h\).

Note

Manipuler un ensemble \(X\) de mots fini ou un morphisme est équivalent: un morphisme est juste une manière de nommer chacun des éléments de \(X\), ce qui est souvent pratique.

Note

Points clefs de la démonstration: faire une récurrence sur la somme des longueurs de mots dans l’image de \(f\). Cas de base: \(f\) est effaçante (il existe \(a\) tel que \(f(a)=\epsilon\)). Sinon la non injectivité force l’existence de \(a\) et \(b\) tels que \(f(a)\) est un préfixe de \(f(b)\) que l’on utilise pour appliquer la récurrence.

Corollaire

Soient \(x\) et \(y\) deux mots non vides. Alors les énoncés suivants sont équivalents:

  1. \(x\) et \(y\) commutent
  2. Il existe \(n,m>0\) tels que \(x^m=y^n\)
  3. Il existe \(z\in A^+\) tels que \(x,y\in z^*\)
  4. \(\{x,y\}\) n’est pas un code ou \(x=y\)

Il existe toute une littérature sur les équations sur les mots.

Conjugaison, périodicité, répétitions
Mots primitifs

Définition

Un mot \(w\in A^+\) est primitif s’il n’est pas la puissance d’un mot plus petit.

Proposition

Soit \(w\in A^+\). Il existe un unique \(z\in A^+\), appelé racine primitive de \(w\), tel que \(z\) est primitif et \(w\in z^*\).

Proposition

Soit \(w\in A^+\). Alors le commutant de \(w\) est donné par \(C(w)=z^*\)\(z\) est la racine primitive de \(w\).

Périodes, répétitions

Définition: période

Soit \(w\in A^*\) et \(x\in A^+\). Alors \(x\) est une période de \(w\) si il existe \(n\in \NN^*\) tel que \(w\) est un préfixe de \(x^n\).

Exemple::

sage: w = Word("abaabaa")
sage: w.periods()
[3, 6]

On note que Sage, comme pas mal de chercheurs, appellent période la longueur du mot \(x\) et non le mot lui-même. Voici les mots correspondants:

sage: w[:3]
word: aba
sage: w[:6]
word: abaaba

On peut avoir directement toutes les périodes comme mots:

sage: [w[:i] for i in w.periods()]
[word: aba, word: abaaba]

Warning

Sage ne considère pas \(w\) comme une période de lui-même!?!

Un autre exemple montrant qu’il n’y a pas forcément une unique période primitive:

sage: w = Word("aaabaaaa")
sage: sage: sage: w.periods()
[5, 6, 7]
sage: [w[:i] for i in w.periods()]
[word: aaaba, word: aaabaa, word: aaabaaa]

Proposition

Soit \(x\in A^+\) et \(w\in A^*\). Les énoncés suivants sont équivalents:

  1. \(x\) est une période de \(w\);
  2. \(w\) est un préfixe de \(xw\);
  3. \(w\) est un préfixe de \(x^nw\) pour tout \(n\).

Théorème (Fine et Wilf, 1965)

Soit \(w\in A^+\) et \(x\) et \(y\) deux périodes distinctes de \(w\) telles que \(|w|\geq |x|+|y|-pgcd(|x|,|y|)\), alors \(x\) et \(y\) ont la même racine primitive.

Exercice:

Montrer que le théorème de Fine & Wilf est optimal, c’est-à-dire que, pour tout \(p,q\) tel que \(pgcd(p,q)<p,q\), il existe un mot \(w\) de longueur \(p+q-pgcd(p,q)-1\) tel que \(w\) est \(p\)-périodique et \(q\)-périodique, mais pas \(pgcd(p,q)\)-périodique.

Indications: commencer par \(p,q\) premiers entre eux et utiliser l’algorithme d’Euclide (version soustractive)

Mots infinis

Définition: topologie sur les mots infinis

Distance entre \(u\) et \(v\): \(2^{-k}\)\(k\) est la position où \(u\) et \(v\) diffèrent.

Lemme de König

Soit \(X\subset A^*\) infini. Alors l’adhérence de \(X\) (dans \(A^\infty\)) contient un mot infini \(w\). Autrement dit une infinité de préfixes de \(w\) sont dans \(X\).

Complexité en facteurs