Factorisation de mots.

Le monoïde libre et les morphismes sont décrits à la page : Monoïde libre. Une application écrite en javascript permet de jouer avec les morphismes de construire des mots, en particulier les suites ou mots de Prouhet-Thue-Morse, de Fibonacci, ou encore la 'Look and Say sequence'.
Inversement, on peut se demander comment trouver un morphisme, le plus simple possible, qui permettrait de construire un mot donné, à partir de sa première lettre, en appliquant un même morphisme plusieurs fois.
Si le mot est fini, il existe évidemment au moins les morphisme triviaux : 1ère lettre -> le mot, mais il y en a peut-être d'autres.

L'idée d'écrire cette page vient de la lecture de l'article 'Inverse problems for finite automata: a solution based on genetic algorithms' de B. Leblanc, E. Lutton, and J.-P. Allouche.
(Le programme ci-dessous s'inspire de la première partie de l'article, de la page 1 à la page 5).

Le programme

On propose un mot à l'application, seuls les 80 premiers caractères seront utilisés (pour éviter un trop long temps d'exécution).
Le programme détermine l'alphabet utilisé et construit aléatoirement une population initiale de 10 morphismes.
Les générations suivantes sélectionneront les morphismes les mieux adaptés.
Les solutions sont les morphismes s qui fixent le mot A donné : s(A) = AB.

[Premier exemple] Les étapes dans l'utilisation de l'application sont : 1 - choix d'un mot (ici un mot de Fibonacci 1011010110110101101011...), 2 - construction de la population initiale, 3 - évolution de la population pour tenter d'obtenir une factorisation.
Le nombre de générations, le nombre d'individus créés, l'alphabet et le mot à atteindre seront affichés sur les premières lignes. Ensuite, sur deux lignes chaque fois, le morphisme, sa valeur (fitness f) et le mot qu'il permet de construire.
Lorsque f > 80 le morphisme trouvé est une solution, dans l'exemple ci-dessous le 73ième individu parmi les 80 créés est une solution :

	  Générations : 10 calculs f : 80 (73) Alphabet : 1 0
	  10110101101101011010110110101101101011010110110101101...
	  -----------------------------
	  1->10 0->1 80.33333333333333
	  10110101101101011010110110101101101011010110110101101...

L'application

Exemples

Créer le mot à factoriser

Dans ce dernier cas, écrire séparément ci-dessous l'alphabet et les images des lettres par le morphisme, le bouton [Mot] permet ensuite d'obtenir un mot de 80 lettres au moins.
- Créer la population : bouton [Initialiser].
- Faire évoluer la population pour tenter de factoriser le mot : bouton [Évoluer].
(On aimerait que le programme détermine un morphisme s aussi simple que possible et non trivial tel que s : A -> AB, le mot A étant un préfixe de son image s(A) = AB).

Quelques mots à essayer de factoriser

(Pour obtenir les générations suivantes, cliquer sur le bouton [Évoluer]).

Mot de Prouhet-Thue-Morse | Initialiser | Évoluer |.

Mot | Initialiser | Évoluer |.

Rudin-Shapiro | Initialiser | Évoluer |.

L'un des mots de la suite 'Look and Say sequence' | Initialiser | Évoluer |.

Mot de Kolakovski | Initialiser | Évoluer |.

Racine carrée de 2 en base 2 (chiffres à droite de la virgule) | Initialiser | Évoluer | Le mot infini ni rationnel, ni transcendant n'est pas factorisable (Loxton et van der Poorten).

La fraction 3/5 mais écrite en base 2 : 11/101 = .100110011001... (chiffres 0 1 seulement) | Initialiser | Évoluer | la fraction est un rationnel, son développement est périodique de période 1001, une factorisation (évidente) est ...

La fraction 9/17 mais écrite en base 3 (chiffres 0 1 2) | Initialiser | Évoluer | Le quotient est un rationnel, son écriture.

Tribonacci : | 1 -> 12, 2 -> 13, 3 -> 1 | Évoluer |.

Morphisme : | 2 -> 231, 1 -> 21, 3 -> 13 | Évoluer |.

(Automaton 1) : | 2 -> 234, 1 -> 61, 3 -> 52, 4 -> 234, 5 -> 6551, 6 -> 433 | Évoluer |.

(Automaton 2) : | 2 -> 24, 1 -> 11116, 3 -> 5, 4 -> 35, 5 -> 2341, 6 -> 666 | Évoluer |.

Morphisme : | 1 -> 1000, 0 -> 11 | Évoluer |.

Morphisme : | 1 -> 123, 2 -> 13, 3 -> 2 | Évoluer |.

Morphisme : | o -> ooI; I -> IoI | Évoluer |.

Morphisme : | 0 -> 012, 1 -> 0, 2 -> 21 | Évoluer |.

Morphisme : | 0 ->01, 1 -> 2, 2 -> 4, 3 -> 34, 4 -> 5, 5 -> 1 | Évoluer |.

Morphisme : | 0 ->01, 1 -> 0 | Évoluer |.

Morphisme : | 0 ->01, 1 -> 100 | Évoluer |.

Morphisme : | 0 ->010, 1 -> 110 | Évoluer |.

Morphisme : | 0 -> 02, 1 -> 12, 2 -> 10 | Évoluer |.

Morphisme : | 0 -> 01, 1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6, 6 -> 0 | Évoluer |.

Liens

19 Inverse problems for finite automata: a solution based on genetic algorithms. B. Leblanc, E. Lutton, and J.-P. Allouche. Lecture Notes in Computer Science (Artificial Evolution, 1997, Eds. J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer, D. Snyers) 1363 (1998), pp. 157-166. (Prétirage/Preprint)

3 Finite automata and morphisms in assisted musical composition. J.-P. Allouche and T. Johnson. Journal of New Music Research 24 (1995), 97-108 et le supplément

les automates finis en mathematiques par Jean-Paul Allouche (MATh.en.JEANS en 1995)

Quasicrystals Uwe Grimm

Fibonacci Chain Steffen Weber. Their ratio L/S is tau=(SQRT(5)+1)/2=1.61803..

Une caractérisation simple des nombres de Sturm C. Allauzen. Journal de Théorie des Nombres de Bordeaux Volume 10 fasc. 2 (1998)

Sequences with subword complexity 2n Günter Rote.

Mots infinis, suites doubles et pavages Laurent Vuillon.

QuasiTiler by Eugenio Durand. QuasiTiler draws Penrose tilings and their generalizations. (Geometry of Quasicrystals).

Pages de liens sur : Fibonacci (nombre d'or), Apériodique (quasicristaux), Polytopes, Algorithmes génétiques, Pavages du plan, Automates.

Mots à deux dimensions représentés par des pavages de Truchet.

Problème inverse de l'automate fini et algorithmes génétiques

Algorithmes génétiques appliqués à la factorisation de mots.