BillaudConjecture < CoWiki

CoWiki Web>AdditionalOpenProblems>BillaudConjecture (2011-09-12, JeffreyShallit) (raw view)

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" _&delta;<sub>x</sub>(w)_ is also morphically primitive. Here _&delta;<sub>x</sub>_ denotes the morphism deleting the letter _x_ (and being identity otherwise).

Perhaps more natural is the original formulation: if _&delta;<sub>x</sub>(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 <br>
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
<br>
Daniel Reidenbach and Johannes C. Schneider. _Morphically primitive words_,
Theor. Comp. Sci. *410* (2009) 2148-2161
<br>
and in
<br>
&#352;t&#283;p&aacute;n Holub, _Polynomial algorithm for fixed points of nontrivial morphisms_, Discrete Mathematics *309* (2009),  5069-5076

-- Main.StepanHolub - 02 Sep 2011

Topic revision: r2 - 2011-09-12 - JeffreyShallit

CoWiki

CoWiki Web
CoWiki Web Home
Changes
Index
Search

Webs
- AIMAS
- CERAS
- CF
- CoWiki
- CrySP
- External
- Faqtest
- HCI
- Himrod
- ISG
- Main
- Multicore
- Sandbox
- TWiki
- TestNewSandbox
- TestWebS
- UW

My links
- People
- CERAS
- WatForm
- Tetherless lab
- Ubuntu Main.HowTo
- eDocs
- RGG NE notes
- RGG
- CS infrastructure
- Grad images

Edit