Decision algorithms for Fibonacci-automatic Words, I: Basic results

Mousavi, Hamoon; Schaeffer, Luke; Shallit, Jeffrey

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 1, pp. 39-66.

We implement a decision procedure for answering questions about a class of infinite words that might be called (for lack of a better name) “Fibonacci-automatic”. This class includes, for example, the famous Fibonacci word $𝐟=f_0{f}_1{f}_2···=01001010···$, the fixed point of the morphism $0\to 01$ and $1\to 0$. We then recover many results about the Fibonacci word from the literature (and improve some of them), such as assertions about the occurrences in $𝐟$ of squares, cubes, palindromes, and so forth.

Classification : 11B85, 68R15, 11A67, 11B39, 03D05, 68Q45
Mots clés : Decision procedure, infinite word, Fibonacci-automatic – square, cube, palindrome, first-order logic, Fibonacci representation – quasiperiod, unbordered word, Lyndon word, uniform recurrence – linear recurrence, critical exponent

C. Ahlbach, J. Usatine, C. Frougny and N. Pippenger, Efficient algorithms for Zeckendorf arithmetic. Fibonacci Quart. 51 (2013) 249–256. | MR | Zbl

J.-P. Allouche, N. Rampersad and J. Shallit, Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci. 410 (2009) 2795–2803. | DOI | MR | Zbl

J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003). | MR | Zbl

J.-P. Allouche, J. Shallit and G. Skordev, Self-generating sets, integers with missing blocks, and substitutions. Discrete Math. 292 (2005) 1–15. | DOI | MR | Zbl

J. Berstel, Mots de Fibonacci. Séminaire d’Informatique Théorique, LITP 6-7 (1980–81) 57–78.

J. Berstel, Fonctions rationnelles et addition. In Théorie des Langages, École de printemps d’informatique théorique, edited by M. Blab. LITP (1982) 177–183.

J. Berstel, Fibonacci Words – A Survey. In The Book of L, edited by G. Rozenberg and A. Salomaa. Springer-Verlag (1986) 13–27. | Zbl

J.-P. Borel and F. Laubie, Quelques mots sur la droite projective réelle. J. Théorie Nombres Bordeaux 5 (1993) 23–51. | DOI | Numdam | MR | Zbl

V. Bruyère, G. Hansel, C. Michaux and R. Villemaire, Logic and $p$-recognizable sets of integers. Bull. Belgian Math. Soc. 1 (1994) 191–238. Corrigendum, Bull. Belg. Math. Soc. 1 (1994) 577. | MR | Zbl

V. Bruyère and G. Hansel, Bertrand numeration systems and recognizability. Theoret. Comput. Sci. 181 (1997) 17–43. | DOI | MR | Zbl

J.R. Büchi, Weak secord-order arithmetic and finite automata. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 6 (1960) 66–92. Reprinted in The Collected Works of J. Richard Büchi, edited by S. Mac Lane and D. Siefkes. Springer-Verlag (1990) 398–424. | DOI | MR | Zbl

L. Carlitz, Fibonacci representations. Fibonacci Quart. 6 (1968) 193–220. | MR | Zbl

J. Cassaigne, Sequences with grouped factors. In Developments in Language Theory III. Aristotle University of Thessaloniki (1998) 211–222.

J. Cassaigne, Recurrence in infinite words. In STACS 2001, edited by A. Ferreira and H. Reichel. Vol. 2010 of Lect. Notes Comput. Sci. Springer-Verlag (2001) 1–11. | MR | Zbl

E. Charlier, N. Rampersad and J. Shallit, Enumeration and decidable properties of automatic sequences. Int. J. Found. Comp. Sci. 23 (2012) 1035–1066. | DOI | MR | Zbl

M. Christou, M. Crochemore and C.S. Iliopoulos, Quasiperiodicities in Fibonacci strings. Preprint arXiv:1201.6162 (2012). To appear in Ars Combinatoria. | MR

W.-F. Chuan, Symmetric Fibonacci words. Fibonacci Quart. 31 (1993) 251–255. | MR | Zbl

A. Cobham, Uniform tag sequences. Math. Systems Theory 6 (1972) 164–192. | DOI | MR | Zbl

L.J. Cummings, D. Moore and J. Karhumäki, Borders of Fibonacci strings. J. Combin. Math. Combin. Comput. 20 (1996) 81–87. | MR | Zbl

J.D. Currie and K. Saari, Least periods of factors of infinite words. RAIRO: ITA 43 (2009) 165–178. | Numdam | MR | Zbl

J.D. Currie, N. Rampersad and K. Saari, Suffix conjugates for a class of morphic subshifts. In WORDS 2013, edited by J. Karhumäki, A. Lepistö and L. Zamboni. Vol. 8079 of Lect. Notes Comput. Sci. Springer-Verlag (2013) 95–106. | MR

A. De Luca, A combinatorial property of the Fibonacci words. Inform. Process. Lett. 12 (1981) 193–195. | DOI | MR | Zbl

X. Droubay, Palindromes in the Fibonacci word. Inform. Process. Lett. 55 (1995) 217–221. | DOI | MR | Zbl

C.F. Du, H. Mousavi, L. Schaeffer and J. Shallit, Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability. In preparation (2016).

C.F. Du, H. Mousavi, L. Schaeffer and J. Shallit, Decision algorithms for Fibonacci-automatic words, III: Enumeration and abelian properties. To appear in Int. J. Found. Comput. Sci (2016). | MR

D.D.A. Epple and J. Siefken, Collapse: A Fibonacci and Sturmian game. Amer. Math. Monthly 122 (2015) 515–527. | DOI | MR | Zbl

S. Fischler, Palindromic prefixes and episturmian words. J. Combin. Theory. Ser. A 113 (2006) 1281–1304. | DOI | MR | Zbl

A.S. Fraenkel, Systems of numeration. Amer. Math. Monthly 92 (1985) 105–114. | DOI | MR | Zbl

A.S. Fraenkel and J. Simpson, The exact number of squares in Fibonacci words. Theoret. Comput. Sci. 218 (1999) 95–106. | DOI | MR | Zbl

C. Frougny, Linear numeration systems of order two. Inform. Comput. 77 (1988) 233–259. | DOI | MR | Zbl

C. Frougny, Fibonacci representations and finite automata. IEEE Trans. Inform. Theory 37 (1991) 393–399. | DOI | MR | Zbl

C. Frougny, Representations of numbers and finite automata. Math. Systems Theory 25 (1992) 37–60. | DOI | MR | Zbl

C. Frougny and B. Solomyak, On representation of integers in linear numeration systems. In Ergodic Theory of $Z^d$ Actions (Warwick, 1993–1994), edited by M. Pollicott and K. Schmidt. Vol. 228 of London Math. Soc. Lect. Note Ser. Cambridge University Press (1996) 345–368. | MR | Zbl

D. Goc, D. Henshall and J. Shallit, Automatic theorem-proving in combinatorics on words. In CIAA 2012, edited by N. Moreira and R. Reis. Vol. 7381 of Lect. Notes Comput. Sci. Springer-Verlag (2012) 180–191. | MR | Zbl

D. Goc, H. Mousavi and J. Shallit, On the number of unbordered factors. In LATA 2013, edited by A.-H. Dediu, C. Martin-Vide, and B. Truthe. Vol. 7810 of Lect. Notes Comput. Sci. Springer-Verlag (2013) 299–310. | MR

D. Goc, K. Saari and J. Shallit, Primitive words and Lyndon words in automatic and linearly recurrent sequences. In LATA 2013, edited by A.-H. Dediu, C. Martin-Vide and B. Truthe. Vol. 7810 of Lect. Notes Comput. Sci. Springer-Verlag (2013) 311–322. | MR

D. Goc, L. Schaeffer and J. Shallit, The subword complexity of $k$-automatic sequences is $k$-synchronized. In DLT 2013, edited by M.-P. Béal and O. Carton. Vol. 7907 of Lect. Notes Comput. Sci. Springer-Verlag (2013) 252–263. | MR

T. Harju and T. Kärki, On the number of frames of binary words. Theoret. Comput. Sci. 412 (2011) 5276–5284. | DOI | MR | Zbl

S. Homer and A.L. Selman, Computability and Complexity Theory, 2nd edition. Springer-Verlag (2011). | MR | Zbl

J.E. Hopcroft, An $nlogn$ algorithm for minimizing the states in a finite automaton. In The Theory of Machines and Computation, edited by Z. Kohavi. Academic Press, New York (1971) 189–196. | MR | Zbl

C.S. Iliopoulos, D. Moore and W.F. Smyth, A characterization of the squares in a Fibonacci string. Theoret. Comput. Sci. 172 (1997) 281–291. | DOI | MR | Zbl

J. Karhumäki, On cube-free $\omega$-words generated by binary morphisms. Disc. Appl. Math. 5 (1983) 279–297. | DOI | MR | Zbl

R. Kolpakov and G. Kucherov, On maximal repetitions in words. In Fundamentals of Computation Theory: FCT ’99, edited by G. Ciobanu and G. Păun. Vol. 1684 of Lect. Notes Comput. Sci. Springer-Verlag (1999) 374–385. | MR | Zbl

C.G. Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci. Simon Stevin 29 (1952) 190–195. | Zbl

F. Levé and G. Richomme, Quasiperiodic infinite words: some answers. Bull. Eur. Assoc. Theor. Comput. Sci. 84 (2004) 128–138. | MR | Zbl

F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. RAIRO: ITA 26 (1992) 199–204. | Numdam | MR | Zbl

F. Mignosi, A. Restivo and M. Sciortino, Words and forbidden factors. Theoret. Comput. Sci. 273 (2002) 99–117. | DOI | MR | Zbl

M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1–42. | DOI | JFM | MR

A. Ostrowski, Bemerkungen zur Theorie der Diophantischen Approximationen. Abh. Math. Sem. Hamburg 1 (1922) 77–98,250–251. Reprinted in Collected Mathematical Papers 3 57–80. | DOI | JFM | MR

G. Pirillo, Fibonacci numbers and words. Discrete Math. 173 (1997) 197–207. | DOI | MR | Zbl

M. Presburger, Über die Volständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In Vol. 395 of Sparawozdanie z I Kongresu matematyków krajów slowianskich. Warsaw (1929) 92–101. | JFM

M. Presburger, On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation. Hist. Phil. Logic 12 (1991) 225–233. | DOI | MR | Zbl

K. Saari, Periods of factors of the Fibonacci word. In WORDS 07 (2007).

K. Saari, Lyndon words and Fibonacci numbers. J. Combin. Theory. Ser. A 121 (2014) 34–44. | DOI | MR | Zbl

L. Schaeffer and J. Shallit, The critical exponent is computable for automatic sequences. Internat. J. Found. Comp. Sci. 23 (2012) 1611–1626. | DOI | MR | Zbl

P. Séébold, Propriétés combinatoires des mots infinis engendrés par certains morphismes. Ph. D. thesis, Université P. et M. Curie, Institut de Programmation, Paris (1985).

J.O. Shallit, A generalization of automatic sequences. Theoret. Comput. Sci. 61 (1988) 1–16. | DOI | MR | Zbl

J. Shallit, Decidability and enumeration for automatic sequences: a survey. In CSR 2013, edited by A.A. Bulatov and A.M. Shur. Vol. 7913 of Lect. Notes Comput. Sci. Springer-Verlag (2013) 49–63. | MR

E. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. Roy. Liège 41 (1972) 179–182. | MR | Zbl