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 (17)

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

This page was built for publication: Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties