Mechanical proofs of properties of the Tribonacci word
From MaRDI portal
Publication:3449367
DOI10.1007/978-3-319-23660-5_15zbMATH Open1350.68218arXiv1407.5841OpenAlexW2963056426MaRDI QIDQ3449367FDOQ3449367
Hamoon Mousavi, Jeffrey Shallit
Publication date: 4 November 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Abstract: We implement a decision procedure for answering questions about a class of infinite words that might be called (for lack of a better name) "Tribonacci-automatic". This class includes, for example, the famous Tribonacci word T = 0102010010202 ..., the fixed point of the morphism 0 -> 01, 1 -> 02, 2 -> 0. We use it to reprove some old results about the Tribonacci word from the literature, such as assertions about the occurrences in T of squares, cubes, palindromes, and so forth. We also obtain some new results.
Full work available at URL: https://arxiv.org/abs/1407.5841
Recommendations
- Decision algorithms for Fibonacci-automatic words. I: Basic results.
- Decision algorithms for Fibonacci-automatic words. III: Enumeration and abelian properties.
- Decision algorithms for Fibonacci-automatic words. II: Related sequences and avoidability
- The numbers of repeated palindromes in the Fibonacci and Tribonacci words
- The Tribonacci substitution
Combinatorics on words (68R15) Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35) Automata sequences (11B85)
Cites Work
- Periodicity, repetitions, and orbits of an automatic sequence
- Automatic Sequences
- Uniform tag sequences
- Episturmian words and some constructions of de Luca and Rauzy
- Logic and \(p\)-recognizable sets of integers
- Some properties of the Tribonacci sequence
- Title not available (Why is that?)
- Balance and abelian complexity of the Tribonacci word
- A morphic approach to combinatorial games: the Tribonacci case
- Combinatorial, ergodic and arithmetic properties of the Tribonacci substitution
- Episturmian words and episturmian morphisms
- Episturmian words: a survey
- Primitive Words and Lyndon Words in Automatic and Linearly Recurrent Sequences
- Quasiperiodic and Lyndon episturmian words
- On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation
- Title not available (Why is that?)
- Representations of numbers and finite automata
- Decidability and Enumeration for Automatic Sequences: A Survey
- A SAT Attack on the Erdős Discrepancy Conjecture
- ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES
- Abelian complexity function of the Tribonacci word
- Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties
- Subword Complexity and k-Synchronization
- Bertrand numeration systems and recognizability
- Automatic Theorem-Proving in Combinatorics on Words
- Title not available (Why is that?)
- Powers in a class of \(\mathcal A\)-strict standard episturmian words
- Title not available (Why is that?)
- On Sturmian and episturmian words, and related topics
- On the Number of Unbordered Factors
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (9)
- The numbers of repeated palindromes in the Fibonacci and Tribonacci words
- Abelian Complexity and Synchronization
- Ostrowski-automatic sequences: theory and applications
- Title not available (Why is that?)
- Prefixes of the Fibonacci word that end with a cube
- First-Order Logic and Numeration Systems
- Queens in exile: non-attacking queens on infinite chess boards
- Deciding game invariance
- Lie complexity of words
This page was built for publication: Mechanical proofs of properties of the Tribonacci word
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449367)
