Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability

We use a decision procedure for the “Fibonacci-automatic” words to solve problems about a number of different sequences. In particular, we prove that there exists an aperiodic infinite binary word avoiding the pattern x x x R. This is the first avoidability result concerning a nonuniform morphism proven purely mechanically.

Authors

• Chen Fei Du
• Hamoon Mousavi
• Eric Rowland
• Luke Schaeffer
• Jeffrey Shallit

Keywords

• Automatic sequence
• Decision procedure
• Avoidability in words
• Finite automata
• Fibonacci representation
• Palindrome