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

DOI10.1051/ITA/2022011zbMATH Open1527.11022arXiv2208.06025WikidataQ123004016 ScholiaQ123004016MaRDI QIDQ6041046FDOQ6041046

Authors: Jeffrey Shallit, Sonja Linghui Shan 

Publication date: 25 May 2023

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

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.

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

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\)

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)

Cites Work

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

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)