A ternary square-free sequence avoiding factors equivalent to abcacba

2016/03/09 by Currie, James D. · 1 citation
#68R15 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1603.03059

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: (1) characterize all the (two-way) infinite ternary square-free words avoiding letter pattern xyzxzyx (2) characterize the lexicographically least (one-way) infinite ternary square-free word avoiding letter pattern xyzxzyx (3) show that the number of ternary square-free words of length n avoiding letter pattern xyzxzyx grows exponentially with n.

Cited by

• Critical exponent of ternary words with few distinct palindromes

Related

• On some interesting ternary formulas
• On the Entropy and Letter Frequencies of Ternary Square-Free Words
• A note on avoidable words in squarefree ternary words
• Infinite ternary square-free words concatenated from permutations of a single word
• Counting ternary square-free words quickly