Sur le problème de l'égalité des facteurs dans les mots morphiques

I. Fagnot

IBP-Litp 1994/63: Rapport de Recherche Litp / Litp research reports
25 pages - Octobre/October 1994 - French document.

PostScript : Ko /Kb

Titre / Title: Sur le problème de l'égalité des facteurs dans les mots morphiques

Résumé : Le problème de l'égalité des facteurs consiste à déterminer si deux mots infinis ont les mêmes facteurs finis. Nous montrons que, sous des hypothèses raisonnables, la décidabilité du problème de l'égalité des facteurs implique celle de l'égalité des mots infinis, un problème dont Culik et Harju ont montré la décidabilité pour les mots morphiques (c'est-à-dire les mots engendrés par morphismes itérés). Nous montrons que le problème de l'égalité des facteurs est décidable pour deux mots morphiques, sous réserve que les morphismes soient primitifs et à délai borné. Nous montrons, de même, que le problème de l'égalité des facteurs est décidable pour tout couple de mots dans le cas d'un alphabet à deux lettres. Nos résultats sont encore vrais dans une version plus forte, à savoir pour le problème de l'inclusion de l'ensemble des facteurs.

Abstract : The subword equivalence problem is the question whether two infinite words have the same finite factors (subwords).We show that, under mild hypotheses, the decidability of the subword equivalence problem implies the decidability of the $\omega$-sequence equivalence problem, a problem which has been shown to be decidable by Culik and Harju for morphic words (i. e. words generated by iterating a morphism). We prove that the subword equivalence problem is decidable for two morphic words, provided the morphisms are primitive and have bounded delays. We also prove that the subword equivalence problem is decidable for any pair of morphic words in the case of a binary alphabet. Our results hold in fact for a stronger version, namely for the subword inclusion problem.

Publications internes Litp 1994 / Litp research reports 1994