On the values attained by a k-regular sequence

AbstractA sequence is said to be k-automatic if the nth term of this sequence is generated by a finite state machine with n in base k as input. Allouche and Shallit first defined k-regular sequences as a natural generalization of k-automatic sequences. We study the set of values attained by a k-regular sequence and characterize sets with the property that any k-regular sequence taking values in this set is necessarily k-automatic. In particular, we show that an unbounded regular sequence must have infinitely many composite values, answering a question of Allouche and Shallit