Cobham’s theorem and its extensions

Jason P. Bell[1]

  • [1] Jason Bell Department of Mathematics Simon Fraser University Burnaby, BC V5A 1S6 Canada

Actes des rencontres du CIRM (2009)

  • Volume: 1, Issue: 1, page 11-16
  • ISSN: 2105-0597

Abstract

top
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.

How to cite

top

Bell, Jason P.. "Cobham’s theorem and its extensions." Actes des rencontres du CIRM 1.1 (2009): 11-16. <http://eudml.org/doc/10001>.

@article{Bell2009,
abstract = {Cobham’s theorem says that if $k$ and $\ell $ are two multiplicatively independent integers and $f(n)$ is a $k$- and $\ell $-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.},
affiliation = {Jason Bell Department of Mathematics Simon Fraser University Burnaby, BC V5A 1S6 Canada},
author = {Bell, Jason P.},
journal = {Actes des rencontres du CIRM},
language = {eng},
month = {3},
number = {1},
pages = {11-16},
publisher = {CIRM},
title = {Cobham’s theorem and its extensions},
url = {http://eudml.org/doc/10001},
volume = {1},
year = {2009},
}

TY - JOUR
AU - Bell, Jason P.
TI - Cobham’s theorem and its extensions
JO - Actes des rencontres du CIRM
DA - 2009/3//
PB - CIRM
VL - 1
IS - 1
SP - 11
EP - 16
AB - Cobham’s theorem says that if $k$ and $\ell $ are two multiplicatively independent integers and $f(n)$ is a $k$- and $\ell $-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.
LA - eng
UR - http://eudml.org/doc/10001
ER -

References

top
  1. B. Adamczewski and J. Bell. Function fields in positive characteristic: expansions and Cobham’s theorem. J. Algebra319 (2008), no. 6, 2337–2350. Zbl1151.11060MR2388308
  2. J.-P. Allouche and J. Shallit. The ring of k -regular sequences. Theoret. Comput. Sci.98 (1992), 163–197. Zbl0774.68072MR1166363
  3. J.-P. Allouche and J. Shallit. Automatic sequences. Theory, applications, generalizations. Cambridge University Press, Cambridge, 2003. Zbl1086.11015MR1997038
  4. P.-G. Becker. K -regular power series and Mahler-type functional equations. J. Number Theory49 (1994), 269–286. Zbl0821.11013MR1307967
  5. J. Bell. A generalization of Cobham’s theorem for regular sequences. Sém. Lothar. Combin. 54A (2005/07), Art. B54Ap, 15 pp. MR2223028
  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. Zbl0668.68005MR971022
  7. B. Bollobás. Graph theory. An introductory course. Springer-Verlag, New York-Berlin, 1979. Zbl0411.05032MR536131
  8. C. Chevalley. Introduction to the Theory of Algebraic Functions of One Variable. Mathematical Surveys No. VI, Amer. Math. Soc., 1951. Zbl0045.32301MR42164
  9. G. Christol. Ensembles presques périodiques k -reconnaissables. Theor. Comput. Sci.9 (1979), 141–145. Zbl0402.68044MR535129
  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. Zbl0472.10035MR614317
  11. A. Cobham. On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory3 (1969), 186–192. Zbl0179.02501MR250789
  12. A. Cobham. Uniform tag sequences. Math. Systems Theory6 (1972), 164–192. Zbl0253.02029MR457011
  13. F. Durand. A generalization of Cobham’s theorem. Theory Comput. Systems31 (1998), 169–185. Zbl0895.68081MR1491657
  14. F. Durand. A theorem of Cobham for non-primitive substitutions. Acta Arith.104 (2002), no. 3, 225–241. Zbl1014.11016MR1914721
  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. Zbl1033.11006MR1990179
  16. S. Fabre. Une généralisation du théorème de Cobham. Acta Arith.67 (1994), 197–208. Zbl0814.11015MR1292734
  17. I. Fagnot. On the subword equivalence problem for morphic words. Discrete Appl. Math.75 (1997), no. 3, 231–253. Zbl0879.68064MR1452927
  18. H. Hahn. Über die nichtarchimedische Größensysteme (1907), reprinted in Gesammelte Abhandlungen I, Springer-Verlag, 1995. 
  19. K. Kedlaya. The algebraic closure of the power series field in positive characteristic.Proc. Amer. Math. Soc.129 (2001), 3461–3470. Zbl1012.12007MR1860477
  20. K. Kedlaya. Finite automata and algebraic extensions of function fields. J. Théor. Nombres Bordeaux18 (2006), 379–420. Zbl1161.11317MR2289431
  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. Zbl0957.16001MR1721834
  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. Zbl0458.10007MR604222
  23. B. Randé. Équations fonctionnelles de Mahler et applications aux suites p -régulières. PhD thesis, Université Bordeaux I, 1992. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.