2022/08/11 by Jeffrey Shallit, Shallit, Jeffrey, Sonja Linghui Shan +3 · 2 citations
Computer Science · Mathematics · #semigroups and automata theory #Computability, Logic, AI Algorithms #Benford’s Law and Fraud Detection
paper · pdf · doi:10.48550/arxiv.2208.06025
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.