TCS Journal 2017 Journal Article
Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability
- Chen Fei Du
- Hamoon Mousavi
- Eric Rowland
- Luke Schaeffer
- Jeffrey Shallit
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.