A Ternary Square-free Sequence Avoiding Factors Equivalent to $abcacba$

James Currie

Abstract


We solve a problem of Petrova, finalizing the classification of letter patterns avoidable by ternary square-free words; we show that there is a ternary square-free word avoiding letter pattern $xyzxzyx$. In fact, we

  • characterize all the (two-way) infinite ternary square-free words avoiding letter pattern $xyzxzyx$
  • characterize the lexicographically least (one-way) infinite ternary square-free word avoiding letter pattern $xyzxzyx$
  • show that the number of ternary square-free words of length $n$ avoiding letter pattern $xyzxzyx$ grows exponentially with $n$.

 


Keywords


Words avoiding patterns, Square-free words

Full Text:

PDF