Séminaire Lotharingien de Combinatoire, B54Ap (2006), 15 pp.
Jason P. Bell
A Generalization of Cobham's Theorem for Regular Sequences
Abstract.
A 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.
A result due to Cobham states that if a sequence is both k- andl-automatic
and k and l 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,l)-regular and k and l
are multiplicatively independent, then the sequence satisfies a linear recurrence over
R.
Received: September 9, 2005.
Accepted: December 23, 2005.
Final Version: January 11, 2006.
The following versions are available: