Logo image
On a conjecture about finite fixed points of morphisms
Article de revue scientifique   Avec comité de lecture

On a conjecture about finite fixed points of morphisms

Gwenaël Richomme et Florence Levé
Theoretical computer science, Vol.339(1), p.103-128
11/06/2005

Résumé

Computer Science Discrete Mathematics
A conjecture of M. Billaud is: Given a word w, if, for each letter x occurring in w, the word obtained by erasing all the occurrences of x in w is a fixed point of a nontrivial morphism fₓ, then w is also a fixed point of a nontrivial morphism. We prove that this conjecture is equivalent to a similar one on sets of words. Using this equivalence, we solve these conjectures in the particular case where each morphism fₓ has only one expansive letter.

Indicateurs

1 Consultations de la notice

Détails

Logo image