Une généralisation du théorème de Cobham

S. Fabre

ArticleOriginal scientific text

Title

Une généralisation du théorème de Cobham

Authors ¹

Affiliations

Université Paris XIII, Département de Mathématiques, Avenue J.-B. Clément, 93430 Villetaneuse, France

Abstract

Nous généralisons le théorème de Cobham ([2]), en démontrant qu'une partie infinie de ℕ est reconnaissable en base k (k entier strictement plus grand que un) et reconnaissable dans un système de numération associé à un nombre de Pisot unitaire (ayant une propriété arithmétique supplémentaire) si et seulement si elle est ultimement périodique.

A. Bertrand, Répartition modulo 1 des suites exponentielles et systèmes dynamiques symboliques, Thèse d'état, Université de Bordeaux 1, 1986.
A. Cobham, On the base dependence of sets of numbers recognizable by finite automata, Math. Systems Theory 3 (1969), 186-192.
A. Cobham, Uniform tag sequence, Math. Systems Theory 6 (1972), 164-192.
S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, 1974.
S. Fabre, Substitutions et β-systèmes de numération, preprint.
C. Frougny, Systèmes de numération linéaires et automates finis , Thèse d'état, Université Paris-VII, 1989.
G. Hansel, A propos d'un théorème de Cobham, Acte de la fête des mots, D. Perrin (ed.), Rouen, 1982, Greco de programmation, C.N.R.S.
B. Mossé, Puissances de mots et reconnaissabilité des points fixes d'une substitution, Theor. Comput. Sci. 99 (1992), 327-334.
W. Parry, On the β-expansions of real numbers, Acta Math. Acad. Sci. Hungar. 11 (1960), 401-416.
M. Queffélec, Substitution Dynamical Systems. Spectral Analysis, Lecture Notes in Math. 1294, Springer, Berlin, 1987.
G. Rauzy, Relations de récurrence modulo m, Séminaire Delange-Pisot, 5ième année (1963-1964), (2-01)-(2-10).
E. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Lièges 3-4 (1960), 179-182.

Title

Une généralisation du théorème de Cobham

Affiliations

Abstract

Bibliography