1. Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties.
- Author
-
Du, Chen Fei, Mousavi, Hamoon, Schaeffer, Luke, and Shallit, Jeffrey
- Subjects
FIBONACCI sequence ,FINITE state machines ,ABELIAN functions ,DECIDABILITY (Mathematical logic) ,DECISION making - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF