Decision algorithms for Fibonacci-automatic Words, I: Basic results
From MaRDI portal
Publication:3186674
DOI10.1051/ita/2016010zbMath1366.68226OpenAlexW2422636290MaRDI QIDQ3186674
Hamoon Mousavi, Luke Schaeffer, Jeffrey O. Shallit
Publication date: 12 August 2016
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1051/ita/2016010
Combinatorics on words (68R15) Formal languages and automata (68Q45) Automata sequences (11B85) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)
Related Items (24)
Decision algorithms for Fibonacci-automatic words. II: Related sequences and avoidability ⋮ The numbers of repeated palindromes in the Fibonacci and Tribonacci words ⋮ Automatic winning shifts ⋮ Properties of a ternary infinite word ⋮ Automatic sequences in negative bases and proofs of some conjectures of shevelev ⋮ The number of valid factorizations of Fibonacci prefixes ⋮ Critical exponents of infinite balanced words ⋮ Prefixes of the Fibonacci word that end with a cube ⋮ Unnamed Item ⋮ On extended boundary sequences of morphic and Sturmian words ⋮ Note on a Fibonacci parity sequence ⋮ An Inequality for the Number of Periods in a Word ⋮ A Fibonacci analogue of the two’s complement numeration system ⋮ A General Approach to Proving Properties of Fibonacci Representations via Automata Theory ⋮ The additive structure of integers with the lower Wythoff sequence ⋮ First-Order Logic and Numeration Systems ⋮ Ostrowski-automatic sequences: theory and applications ⋮ On prefix palindromic length of automatic words ⋮ Additive number theory via automata theory ⋮ Deciding game invariance ⋮ Unnamed Item ⋮ Subword complexity of the Fibonacci-Thue-Morse sequence: the proof of Dekking's conjecture ⋮ Unnamed Item ⋮ Sumsets of Wythoff sequences, Fibonacci representation, and beyond
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Decision algorithms for Fibonacci-automatic words. II: Related sequences and avoidability
- Lyndon words and Fibonacci numbers
- On the number of frames in binary words
- Palindromic prefixes and episturmian words
- Linear numeration systems of order two
- A generalization of automatic sequences
- A combinatorial property of the Fibonacci words
- The exact number of squares in Fibonacci words
- Certain words on the real projective line
- Logic and \(p\)-recognizable sets of integers
- Palindromes in the Fibonacci word
- Fibonacci numbers and words
- Bertrand numeration systems and recognizability
- A characterization of the squares in a Fibonacci string
- Words and forbidden factors
- Self-generating sets, integers with missing blocks, and substitutions
- On cube-free \(\omega\)-words generated by binary morphisms
- Periodicity, repetitions, and orbits of an automatic sequence
- The Critical Exponent is Computable for Automatic Sequences
- Suffix Conjugates for a Class of Morphic Subshifts
- Efficient Algorithms for Zeckendorf Arithmetic
- Automatic Theorem-Proving in Combinatorics on Words
- Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties
- Fibonacci representations and finite automata
- Weak Second‐Order Arithmetic and Finite Automata
- Collapse: A Fibonacci and Sturmian Game
- Least Periods of Factors of Infinite Words
- Systems of Numeration
- On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation
- Representations of numbers and finite automata
- Repetitions in the Fibonacci infinite word
- Automatic Sequences
- ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES
- On the Number of Unbordered Factors
- Primitive Words and Lyndon Words in Automatic and Linearly Recurrent Sequences
- Decidability and Enumeration for Automatic Sequences: A Survey
- Uniform tag sequences
- Symbolic Dynamics II. Sturmian Trajectories
This page was built for publication: Decision algorithms for Fibonacci-automatic Words, I: Basic results