There are k-uniform cubefree binary morphisms for all k >= 0

2008/12/24 by James Currie, Narad Rampersad, Currie, James +1
Computer Science · Mathematics · #68R15 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #cs.FL #math.CO #msc:68R15

paper · pdf · doi:10.48550/arxiv.0812.4470

5 pages

arxiv created 2008/12/24 · arxiv updated 2009/12/01

Abstract

A word is cubefree if it contains no non-empty subword of the form xxx. A morphism h : Sigma^* -> Sigma^* is k-uniform if h(a) has length k for all a in Sigma. A morphism is cubefree if it maps cubefree words to cubefree words. We show that for all k >= 0 there exists a k-uniform cubefree binary morphism.

Related

• Another Solution to the Thue Problem of Non-Repeating Words
• Cubefree binary words avoiding long squares
• Power-free Complementary Binary Morphisms
• Cubefree words with many squares
• Existence of finite test-sets for k-power-freeness of uniform morphisms