2025/12/10 by Moradi, Delaram, Rampersad, Narad, Shallit, Jeffrey
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Number Theory (math.NT)
paper · doi:10.48550/arxiv.2512.10017
We construct automata with input(s) in base k recognizing some basic relations and study their number of states. We also consider some basic operations on k-automatic sequences and discuss their state complexity. We find a relationship between subword complexity of the interior sequence (h'(i))i ≥ 0 and state complexity of the linear subsequence (h(ni+c))i ≥ 0. We resolve a recent question of Zantema and Bosma about linear subsequences of k-automatic sequences with input in most-significant-digit-first format. We also discuss the state complexity and runtime complexity of using a reasonable interpretation of Büchi arithmetic to actually construct some of the studied automata recognizing relations or carrying out operations on automatic sequences.