Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties

DOI10.1142/S0129054116500386zbMath1366.68224OpenAlexW2590512199MaRDI QIDQ2974059

Hamoon Mousavi, Luke Schaeffer, Chen Fei Du, Jeffrey O. Shallit

Publication date: 6 April 2017

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054116500386

zbMATH Keywords

first-order logicsquaredecidabilityfinite automatonFibonacci sequencesubword complexitycubeFibonacci worddecision procedureFibonacci representationbalanced wordabelian squareFibonacci-automatic wordmaximal repetitionabelian cubeFibonacci-regular sequencesynchronized automatonZeckendorf-representation

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Automata sequences (11B85) Other number representations (11A67)

Related Items

Abelian-square-rich words, Prefix palindromic length of the Thue-Morse word, Mechanical Proofs of Properties of the Tribonacci Word, Decision algorithms for Fibonacci-automatic Words, I: Basic results, Robbins and Ardila meet Berstel, Möbius orthogonality for the Zeckendorf sum-of-digits function, Critical exponents of infinite balanced words, Two-dimensional Fibonacci words: tandem repeats and factor complexity, The additive structure of integers with the lower Wythoff sequence, Ostrowski-automatic sequences: theory and applications, On prefix palindromic length of automatic words, Additive number theory via automata theory, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Ostrowski numeration systems, addition, and finite automata, Subword complexity of the Fibonacci-Thue-Morse sequence: the proof of Dekking's conjecture, Queens in exile: non-attacking queens on infinite chess boards, Sumsets of Wythoff sequences, Fibonacci representation, and beyond

Cites Work

• On factors of synchronized sequences
• An optimal algorithm for computing the repetitions in a word
• The exact number of squares in Fibonacci words
• On synchronized sequences and their separators
• ON THE REPETITIVITY INDEX OF INFINITE WORDS
• ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES
• On the Number of Unbordered Factors
• Subword Complexity and k-Synchronization
• Symbolic Dynamics II. Sturmian Trajectories