Mechanical Proofs of Properties of the Tribonacci Word

2014/07/22 by Hamoon Mousavi, Jeffrey Shallit, Mousavi, Hamoon +1 · 2 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #cs.DM #cs.FL #math.CO

paper · pdf · doi:10.48550/arxiv.1407.5841

arXiv admin note: substantial text overlap with arXiv:1406.0670

arxiv created 2014/07/27 · arxiv updated 2014/07/29

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.

Citations

• Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance

Cited by

• On a sequence of Kimberling and its relationship to the Tribonacci word
• Deconstructing Subset Construction -- Reducing While Determinizing

Related

• Some Tribonacci Conjectures
• Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance
• The numbers of distinct and repeated squares and cubes in the Tribonacci sequence
• The numbers of powers in the Tribonacci sequence
• The Tribonacci and ABC Representations of Numbers are Equivalent