9
$\begingroup$

A word is cubefree if it cannot be written as $xyyyz$ where $y$ has positive length.

Let $h$ be the morphism from $\{0,1,2,3,4\}^*$ to $\{0,1\}^*$ given for words of length 1 as follows ($a\to h(a)$): $$0\to 001001010011$$ $$1\to 001001101011$$ $$2\to 001010011011$$ $$3\to 001101001011$$ $$4\to 010011001011$$ and extending to longer words by the morphism property $h(xy)=h(x)h(y)$.

Is it cubefree-preserving? That is, if $x$ is cubefree then is $h(x)$ cubefree?

(I checked that it is so for $x$ of length at most 8; in general there is no finite test set by a result of Richomme and Wlazinski, but maybe there's something special about this case.)

And if not this map...

does there exist any cubefree-preserving map from an alphabet of size 5 to an alphabet of size 2?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

An $\infty$ to 2 (hence 5 to 2) cube-free morphism was constructed by Bean-Ehrenfeucht-McNulty. The fact that your morphism is cube-free follows from their theorem. See Theorem 2.4.1 of my book "Combinatorial Algebra:syntax and semantics".

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Couldn't ask for more! $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Apr 20, 2020 at 12:32
  • $\begingroup$ Another construction for such a morphism can be found in Theorem 6 of F.-J. Brandenburg, Uniformly growing k-th power-free homomorphisms, Theoret. Comput. Sci. 23 (1893), 69-82. $\endgroup$
    – Narad Rampersad
    Commented Apr 21, 2020 at 9:10
1
$\begingroup$

It shouldn't be hard to prove that your morphism is cube-free. Basically you have to check that for all letters $a,b,c$ you can't find an occurrence of $h(c)$ in $h(ab)$, except as a prefix or suffix, and further, if $h(a)=st$, $h(b)=uv$, and $h(c)=sv$, then either $a=c$ or $b=c$. If that holds then a standard argument shows that $h$ is cube-free. For example, see some of the proofs in N. Rampersad, J. Shallit, M.-w. Wang, "Avoiding large squares in infinite binary words", Theoret. Comput. Sci. 339 (2005), 19-34.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .