Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties
Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, Jeffrey O. Shallit · International Journal of Foundations of Computer Science · 2016
We continue our study of the class of Fibonacci-automatic words. These are infinite words whose nth term is defined in terms of a finite-state function of the Fibonacci representation of n. In this paper, we show how enumeration questions (such as counting the number of squares of length n in the Fibonacci word) can be decided purely mechanically, using a decision procedure. We reprove some known results, in a unified way, using our technique, and we prove some new results. We also examine abelian properties of these words. As a consequence of our results on abelian properties, we get the result that every nontrivial morphic image of the Fibonacci word is Fibonacci-automatic.