Sur les facteurs des mots automatiques

I. FAGNOT

IBP-Litp 1995/06: Rapport de Recherche Litp / Litp research reports
27 pages - Février/February 1995 - French document.

PostScript : Ko /Kb

Titre / Title: Sur les facteurs des mots automatiques

Résumé : Le problème de l'égalité des facteurs consiste à déterminer si deux mots infinis ont les mêmes facteurs finis. Ce problème est décidable pour deux mots automatiques. Nous démontrons aussi un théorème 'à la Cobham' : soient k et l deux entiers multiplicativement indépendants et soient x un mot k-automatique et y un mot l-automatique. Si x et y ont les mêmes facteurs, alors ils sont tous les deux ultimement périodiques.

Abstract : The subword equivalence problem is to decide whether two words have the same finite factors. This problem is decidable for two automatic words. We also show a 'Cobham-like' theorem : let k and l be two multiplicatively independant integers and let x be a k-automatic word and y be an l-automatic word. If x and y have the same factors, then both of them are ultimately periodics.

Publications internes Litp 1995 / Litp research reports 1995