A word
w is said to be
morphically imprimitive if there is a non-identity morphism
f fixing it, that is,
f(w)=w. Otherwise (that is, if it is fixed only trivially - by the identity), it is called
morphically primitive.
A conjecture attributed to M. Billaud states that if a word is morphically primitive, then at least one of its "heirs"
δx(w) is also morphically primitive. Here
δx denotes the morphism deleting the letter
x (and being identity otherwise).
Perhaps more natural is the original formulation: if
δx(w) is morphically imprimitive for all letters
x occurring in
w, then also
w is morphically imprimitive.
The conjecture was formulated in 1993 and is believed to be difficult. It easily holds if the alphabet of
w has cardinality at most three (Zimmermann, 1993).
Some special cases were solved in
F. Levé and G. Richomme.
On a conjecture about finite fixed points of morphisms, Theor. Comp. Sci.
339 (2005) 103-128
Some insight into morphical (im)primitivity, so far insufficient to solve the conjecture, was recently
obtained in
Daniel Reidenbach and Johannes C. Schneider.
Morphically primitive words,
Theor. Comp. Sci.
410 (2009) 2148-2161
and in
Štěpán Holub,
Polynomial algorithm for fixed points of nontrivial morphisms, Discrete Mathematics
309 (2009), 5069-5076
--
StepanHolub - 02 Sep 2011