A GENERALIZATION OF COBHAM'S THEOREM FOR REGULAR SEQUENCES
Jason P. Bell · Séminaire Lotharingien de Combinatoire [electronic only] · 2005
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 k- and '-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.