Suite d'Ehrenfeucht-Mycielski
From Wikipedia, the free encyclopedia
La suite d'Ehrenfeucht-Mycielski (en anglais « Ehrenfeucht-Mycielski sequence » est une suite binaire qui a des propriétés qui ressemblent à celles de suites pseudo-aléatoires. Elle a été définie par Andrzej Ehrenfeucht et Jan Mycielski en 1992[1].
La suite commence avec le bit 0 ; chaque bit est calculé en fonction des bits précédents : on cherche le plus long suffixe qui apparaît déjà une autre fois dans la suite, et on ajoute le bit qui ne suit pas cette autre occurrence (s'il y a plusieurs occurrences, on prend la dernière).
Par exemple, pour la suite
- 01001101011100010000111
le plus long suffixe qui apparaît déjà une autre fois dans ce mot est 0111 puisque l'on a :
- 01001101011100010000111
Son occurrence autre que la dernière est suivie de 0, donc la suite continue par 1 et devient
- 010011010111000100001111
Construction de la suite
Le principe décrit ci-dessus donne successivement les bits suivant :
- 0 : bit initial ; le mot vide est le suffixe qui apparaît déjà, il est suivi de 0 donc on ajoute 1
- 01 : à nouveau, seul le mot vide apparaît déjà, sa dernière occurrence est suivie de 1 donc on ajoute 0
- 010 : le suffixe 0 apparaît suivi de 1, donc on ajoute 0
- 0100 : le suffixe 0 apparaît deux fois, la dernière fois suivi de 0, donc on ajoute 1
- 01001 : le suffixe 01 apparaît suivi de 0, donc on ajoute 1
- 010011 : le suffixe 1 apparaît deux fois, la dernière fois suivi de 1, donc on ajoute 0
- 0100110 : etc.
Les premiers termes de la suite sont :
- 0100110101110001000011110110010100100111010001100...
C'est la suite A038219 de l'OEIS. Une variante de la suite est obtenue en remplaçant (0,1) par (1,2) : c'est la suite A007061 de l'OEIS :
- 121122121222111211112222...
On a aussi calculé la suite de plages formée par des symboles identiques consécutifs (suite des runs du run-length encoding, c'est la suite A201881 de l'OEIS :
- 11221113314412211...
Algorithme
L'algorithme naïf calcule un bit de la suite en comparant chaque suffixe à la séquence tout entière. Il prend un temps en O(n3) pour engendrer les n premiers termes. De fait, une structure de donnée similaire à un arbre des suffixes permet d'engendrer la suite en temps constant par bit engendré[2].
Universalité
La suite d'Ehrenfeucht-Mycielski est une suite univers ; elle a la propriété que toute suite finie de bits y apparaît comme facteur une infinité de fois[3]. Une telle suite est parfois appelée disjonctive. De manière équivalente, le nombre 0.01001101... dont la suite est le développement en base 2 est un nombre univers. Il a été calculé[2] que tout facteur de longueur i apparaît au moins j fois dans le préfixe de longueur A(4i,j) de la suite, où A est la fonction d'Ackermann, mais des observations expérimentales suggèrent une borne bien meilleure : la longueur d'un préfixe contenant tous les mots de longueur i en facteur semble être proche de la plus petite valeur possible, à savoir 2i + i, celle des suites de de Bruijn[4].
