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

Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2011-09-12 - JeffreyShallit
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback