Automatic sequences in negative bases and proofs of some conjectures of shevelev

DOI10.1051/ITA/2022011MaRDI QIDQ6041046zbMATH OpenWikidataFDO

Authors Jeffrey Shallit, Sonja Linghui Shan

Publication date 25 May 2023

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2208.06025

zbMATH Keywords

automatic sequencecombinatorics on wordsdecision procedureFibonacci representationlogicrepresentation in negative baseThue-Morse sequence

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Radix representation; digital problems (11A63) Automata sequences (11B85) Formal languages and automata (68Q45) Combinatorics on words (68R15)

Abstract: We discuss the use of negative bases in automatic sequences. Recently the theorem-prover Walnut has been extended to allow the use of base (-k) to express variables, thus permitting quantification over Z instead of N. This enables us to prove results about two-sided (bi-infinite) automatic sequences. We first explain the theory behind negative bases in Walnut. Next, we use this new version of Walnut to give a very simple proof of a strengthened version of a theorem of Shevelev. We use our ideas to resolve two open problems of Shevelev from 2017. We also reprove a 2000 result of Shur involving bi-infinite binary words.

Recommendations

• Fife's theorem for 73-powers
• Repetitions in infinite palindrome-rich words
• On highly repetitive and power free words
• A generator of morphisms for infinite words
• Infinite words containing squares at every position
• Concerning Kurosaki's squarefree word
• Attainable lengths for circular binary words avoiding \(k\) powers
• Construction of a bi-infinite power free word with a given factor and a non-recurrent letter
• Fewest repetitions in infinite binary words
• On the number of \(\alpha \)-power-free binary words for \(2<\alpha \leq 7/3\)

Cites work

• A numeration system for Fibonacci-like Wang shifts
• Automatic Sequences
• Decision algorithms for Fibonacci-automatic words. I: Basic results.
• Differences of multiple Fibonacci numbers
• scientific article; zbMATH DE number 5604127 (Why is no real title available?)
• scientific article; zbMATH DE number 3661611 (Why is no real title available?)
• scientific article; zbMATH DE number 58834 (Why is no real title available?)
• scientific article; zbMATH DE number 1740032 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 3397597 (Why is no real title available?)
• scientific article; zbMATH DE number 3076700 (Why is no real title available?)
• scientific article; zbMATH DE number 7663612 (Why is no real title available?)
• On the existence of solutions for the Frenkel-Kontorova models on quasi-crystals
• Subword complexity and power avoidance
• Synchronized sequences
• The structure of the set of cube-free Z-words in a two-letter alphabet
• The Tribonacci substitution

Cited in

(7)

• Some tribonacci conjectures
• Proving results about OEIS sequences with \texttt{Walnut}
• Proving properties of some greedily-defined Integer recurrences via automata theory
• Rarefied Thue-Morse sums via automata theory and logic
• The Pell tower and Ostronometry
• Self-verifying predicates in Büchi arithmetic
• Balanced Fibonacci word rectangles, and beyond

This page was built for publication: Automatic sequences in negative bases and proofs of some conjectures of shevelev

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041046)