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

Perhaps more natural is the original formulation: if *δ _{x}(w)* is morphically imprimitive for all letters

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

Copyright © 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

Ideas, requests, problems regarding TWiki? Send feedback