Séminaire Lotharingien de Combinatoire 54A (2006), Article B54Ap A GENERALIZATION OF COBHAM’S THEOREM FOR REGULAR SEQUENCES

Abstract. A sequence is said to be k-automatic if the n th term of this sequence is generated by a finite state machine with n in base k as input. A result due to Cobham states that if a sequence is both kand ℓ-automatic and k and ℓ are multiplicatively independent, then the sequence is eventually periodic. Allouche and Shallit defined (R, k)-regular sequences as a natural generalization of k-automatic sequences for a given ring R. In this paper we prove the following generalization of Cobham’s theorem: If a sequence is (R, k)- and (R, ℓ)-regular and k and ℓ are multiplicatively independent, then the sequence satisfies a linear recurrence over R. 1