Substitutions and \(\beta\) systems of numeration. (Substitutions et \(\beta\)-systèmes de numération.) (French) Zbl 0872.11017

Fabre, Stéphane

Theor. Comput. Sci. 137, No. 2, 219-236 (1995).

Summary: Dans son fameux article, Cobham a montré que la suite des états d’un \(k\)-automate était le point fixe d’une substitution de longueur constante [A. Cobham, Math. Systems Theory 6, 164-192 (1972; Zbl 0253.02029)]. Après avoir introduit de nouvelles notions (substitution de longueur \(\theta\), suite \(\theta\)-automatique\(\ldots \)), nous donnons un théorème analogue pour les systèmes de numération associés à des \(\beta\)-nombres.

MSC:

11B85	Automata sequences
68R99	Discrete mathematics in relation to computer science
11A67	Other number representations

Keywords:

Cobham’s theorem; substitution; automatic sequence; numeration systems

Citations:

Zbl 0253.02029

References:

[2]	Cobham, A., Uniform tag sequences, Mathe. System Theory, 6, 164-192 (1972) · Zbl 0253.02029
[3]	Eilenberg, S., (Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[4]	Frougny, C., Systèmes de numération linéaires et automates finis, (Thèse d’Etat (1986), Université Paris-VII)
[5]	Parry, W., On the β-expensions of real numbers, Acta Math. Acad. Sci. Hungar, 11, 401-416 (1960) · Zbl 0099.28103
[7]	Renyi, A., Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hungar, 8, 477-493 (1957) · Zbl 0079.08901
[8]	Shallit, J., A généralization of automatic sequences, Theoret. Comput. Sci., 61, 1-16 (1988) · Zbl 0662.68052
[9]	Zeckendorf, E., Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Royale des Sciences de Lièges, 3-4, 179-182 (1960) · Zbl 0252.10011