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

combinatorics on wordsautomatic sequencelogicThue-Morse sequencedecision procedureFibonacci representationrepresentation in negative base

Mathematics Subject Classification ID

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

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 \(\frac 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

• 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?)
• A numeration system for Fibonacci-like Wang shifts
• Automatic Sequences
• Decision algorithms for Fibonacci-automatic words. I: Basic results.
• Differences of multiple Fibonacci numbers
• On the existence of solutions for the Frenkel-Kontorova models on quasi-crystals
• Subword complexity and power avoidance
• Synchronized sequences
• The Tribonacci substitution
• The structure of the set of cube-free \(Z\)-words in a two-letter alphabet

Cited in

(4)

• Proving properties of some greedily-defined Integer recurrences via automata theory
• Some tribonacci conjectures
• Rarefied Thue-Morse sums via automata theory and logic
• Proving results about OEIS sequences with \texttt{Walnut}

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)