Complexity of Linear Subsequences of $k$-Automatic Sequences
This work addresses theoretical questions in automata theory and formal languages, likely incremental as it builds on existing concepts to provide new insights.
The paper tackles the problem of analyzing the complexity of linear subsequences in k-automatic sequences, resolving a specific question about their properties and establishing a relationship between subword complexity and state complexity.
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 $(h(i))_{i \geq 0}$ and discuss their state complexity. We find a relationship between subword complexity of the interior sequence $(h'(i))_{i \geq 0}$ and state complexity of the linear subsequence $(h(ni+c))_{i \geq 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.