Facteurs spéciaux et complexité

Abstract

Français

On appelle complexité d'une suite infinie 11 ft valeurs dam,un ens<::mble fini. la fonction P11 qui compte le nombre de facteurs de longueur donnée de celle suite. Nous décr ivons ici une méthode récuJTcntc de construction des facteurs spéciaux de suites autOmatiques qui permet de trouver des formule:--  explicites pour la complexl!é de certaines suites.

Anglais

ll1c comple\ity of an 1nfinite seq uence 11 taking lh 'aluc in a lml!c  ct cnunts the numhcr 1'

1n) of fac ­

11

 

tnr' ni" a g1H:n lcngth 11 of this sequence. We dcscnhc hère an Jnducti\C mcthnd tn con truct the special factors of sorne auwmat ic cqucnces \\ hich alln\1 lh hl cumputc the complc\Îl) fu net ion of snmc scqucncc,.,.