#####
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 *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*l*-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: