Complexity of Linear Subsequences of $k$-Automatic Sequences

Abstract

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\ge 0}$ and discuss their state complexity. We find a relationship between subword complexity of the interior sequence $(h^{\prime }(i){)}_{i\ge 0}$ and state complexity of the linear subsequence $(h(ni+c){)}_{i\ge 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.

Fixed some typos and other minor inaccuracies