Mersenne banner
no. 1
Cobham’s theorem and its extensions
Jason P. Bell1
1 Jason Bell Department of Mathematics Simon Fraser University Burnaby, BC V5A 1S6 Canada
Actes des rencontres du CIRM, Volume 1 (2009) no. 1, pp. 11-16.

Cobham’s theorem says that if k and ℓ are two multiplicatively independent integers and f(n) is a k- and ℓ-automatic sequence, then f(n) is eventually periodic. We give a summary of recent work on automatic sequences and their relation to Cobham’s theorem.

Published online:
DOI: 10.5802/acirm.3
Jason P. Bell 1

1 Jason Bell Department of Mathematics Simon Fraser University Burnaby, BC V5A 1S6 Canada 
@article{ACIRM_2009__1_1_11_0,
     author = {Jason P. Bell},
     title = {Cobham{\textquoteright}s theorem and its extensions},
     journal = {Actes des rencontres du CIRM},
     pages = {11--16},
     publisher = {CIRM},
     volume = {1},
     number = {1},
     year = {2009},
     doi = {10.5802/acirm.3},
     zbl = {1451.11018},
     language = {en},
     url = {https://acirm.centre-mersenne.org/articles/10.5802/acirm.3/}
}
TY  - JOUR
AU  - Jason P. Bell
TI  - Cobham’s theorem and its extensions
JO  - Actes des rencontres du CIRM
PY  - 2009
SP  - 11
EP  - 16
VL  - 1
IS  - 1
PB  - CIRM
UR  - https://acirm.centre-mersenne.org/articles/10.5802/acirm.3/
DO  - 10.5802/acirm.3
LA  - en
ID  - ACIRM_2009__1_1_11_0
ER  - 
%0 Journal Article
%A Jason P. Bell
%T Cobham’s theorem and its extensions
%J Actes des rencontres du CIRM
%D 2009
%P 11-16
%V 1
%N 1
%I CIRM
%U https://acirm.centre-mersenne.org/articles/10.5802/acirm.3/
%R 10.5802/acirm.3
%G en
%F ACIRM_2009__1_1_11_0
Jason P. Bell. Cobham’s theorem and its extensions. Actes des rencontres du CIRM, Volume 1 (2009) no. 1, pp. 11-16. doi : 10.5802/acirm.3. https://acirm.centre-mersenne.org/articles/10.5802/acirm.3/

[1] B. Adamczewski and J. Bell. Function fields in positive characteristic: expansions and Cobham’s theorem. J. Algebra 319 (2008), no. 6, 2337–2350. | DOI | MR | Zbl

[2] J.-P. Allouche and J. Shallit. The ring of k-regular sequences. Theoret. Comput. Sci. 98 (1992), 163–197. | DOI | MR | Zbl

[3] J.-P. Allouche and J. Shallit. Automatic sequences. Theory, applications, generalizations. Cambridge University Press, Cambridge, 2003. | DOI | Zbl

[4] P.-G. Becker. K-regular power series and Mahler-type functional equations. J. Number Theory 49 (1994), 269–286. | DOI | MR | Zbl

[5] J. Bell. A generalization of Cobham’s theorem for regular sequences. Sém. Lothar. Combin. 54A (2005/07), Art. B54Ap, 15 pp. | Zbl

[6] J. Berstel and C. Reutenauer. Rational Series and Their Languages EATCS Monographs on Theoretical Computer Science (12), W. Brauer, G. Rozenberg, A. Saloma (Eds.) Springer-Verlag Berlin, Heidelberg 1988. | Zbl

[7] B. Bollobás. Graph theory. An introductory course. Springer-Verlag, New York-Berlin, 1979. | Zbl

[8] C. Chevalley. Introduction to the Theory of Algebraic Functions of One Variable. Mathematical Surveys No. VI, Amer. Math. Soc., 1951.

[9] G. Christol. Ensembles presques périodiques k-reconnaissables. Theor. Comput. Sci. 9 (1979), 141–145. | DOI | MR | Zbl

[10] G. Christol, T. Kamae, M. Mendès France & G. Rauzy. Suites algébriques, automates et substitutions. Bull. Soc. Math. France 108 (1980), 401–419. | DOI | Zbl

[11] A. Cobham. On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3 (1969), 186–192. | DOI | MR | Zbl

[12] A. Cobham. Uniform tag sequences. Math. Systems Theory 6 (1972), 164–192. | DOI | MR | Zbl

[13] F. Durand. A generalization of Cobham’s theorem. Theory Comput. Systems 31 (1998), 169–185. | DOI | MR | Zbl

[14] F. Durand. A theorem of Cobham for non-primitive substitutions. Acta Arith. 104 (2002), no. 3, 225–241. | DOI | MR | Zbl

[15] G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward. Recurrence sequences. Mathematical Surveys and Monographs, 104. American Mathematical Society, Providence, RI, 2003. | Zbl

[16] S. Fabre. Une généralisation du théorème de Cobham. Acta Arith. 67 (1994), 197–208. | DOI | Zbl

[17] I. Fagnot. On the subword equivalence problem for morphic words. Discrete Appl. Math. 75 (1997), no. 3, 231–253. | DOI | MR | Zbl

[18] H. Hahn. Über die nichtarchimedische Größensysteme (1907), reprinted in Gesammelte Abhandlungen I, Springer-Verlag, 1995. | DOI

[19] K. Kedlaya. The algebraic closure of the power series field in positive characteristic.Proc. Amer. Math. Soc. 129 (2001), 3461–3470. | DOI | MR | Zbl

[20] K. Kedlaya. Finite automata and algebraic extensions of function fields. J. Théor. Nombres Bordeaux 18 (2006), 379–420. | DOI | MR | Zbl

[21] G. Krause and T. Lenagan. Growth of Algebras and Gelfand–Kirillov Dimension, revised edition. Grad. Stud. Math., vol. 22, Amer. Math. Soc., Providence, RI, 2000. | Zbl

[22] M. Mendès France. Sur les décimales des nombres algébriques réels, in Sémin. Théor. Nombres, Bordeaux, 1979–1980, Exp. No. 28, 7 pp., Univ. Bordeaux I, Talence, 1980. | Zbl

[23] B. Randé. Équations fonctionnelles de Mahler et applications aux suites p-régulières. PhD thesis, Université Bordeaux I, 1992.

Cited by Sources: