Confluent linear numeration systems. (English) Zbl 0787.68057

Summary: Numeration systems where the basis is defined by a linear recurrence with integer coefficients are considered. A rewriting system is associated with the recurrence. We study the case when it is confluent. We prove that the function of normalization which transforms any representation of an integer into the normal one – obtained by the usual algorithm – can be realized by a finite automaton which is the composition of a left subsequential transducer and of a right subsequential transducer associated with the rewriting system. Addition of integers in a confluent linear numeration system is also computable by a finite automaton. These results extend to the representation of real numbers in basis \(\theta\), where \(\theta\) is the dominant root of the characteristic polynomial of the recurrence.


68Q42 Grammars and rewriting systems
Full Text: DOI


[1] Beauquier, D.; Perrin, D., Codeterministic automata on infinite words, Inform. Process. Lett., 20, 95-98 (1985) · Zbl 0571.68073
[2] Berstel, J., Transductions and Context-Free Languages (1979), Teubner: Teubner Leipzig · Zbl 0424.68040
[3] Berstel, J., Fibonacci words — A survey, (Rozenberg, G.; Salomaa, A., The Books of L (1986), Springer: Springer Berlin), 13-27 · Zbl 0589.68053
[4] A. Bertrand-Mathis, Le θ-shift sans peine, to appear.; A. Bertrand-Mathis, Le θ-shift sans peine, to appear.
[5] A. Bertrand-Mathis, Comment écrire les nombres entiers dans une base qui ne l’est pas, to appear.; A. Bertrand-Mathis, Comment écrire les nombres entiers dans une base qui ne l’est pas, to appear. · Zbl 0695.10005
[6] Blanchard, F., β-expansions and symbolic dynamics, Theoret. Comput. Sci., 65, 131-141 (1989) · Zbl 0682.68081
[7] Choffrut, Ch., Une caractérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations, rationnelles, Theoret. Comput. Sci., 5, 325-337 (1977) · Zbl 0376.94022
[8] Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[9] Elgot, C. C.; Mezei, J. E., On relations defined by generalized finite automata, IBM J. Res. Develop., 9, 47-68 (1965) · Zbl 0135.00704
[10] Frougny, Ch., Systèmes de numération linéaires et automates finis, Thèse d’Etat (1989), Université Paris 7, Rapport LITP 89-69
[11] Frougny, Ch., Fibonacci representations and finite automata, IEEE Trans. Inform. Theory, 37, 2, 393-399 (1991) · Zbl 0716.68067
[12] Ch. Frougny, Representations of numbers and finite automata, Math. Systems Theory; Ch. Frougny, Representations of numbers and finite automata, Math. Systems Theory
[13] Gire, F., Relations rationnelles infinitaires, (Thèse de 3e cycle (1981)), Université Paris 7 · Zbl 0552.68064
[14] Huet, G., Confluent reductions: Abstract properties and applications to term rewriting systems, J. Assoc. Comput. Mach., 27, 797-821 (1980) · Zbl 0458.68007
[15] Knuth, D. E., The art of computer programming, Vols. 1, 2 and 3 (1975), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0191.17903
[16] Knuth, D. E.; Bendix, P. B., Simple word problems in universal algebras, (Leech, J., Computational Problems in Abstract Algebra (1970), Pergamon Press: Pergamon Press Oxford), 263-297 · Zbl 0188.04902
[17] Parry, W., On the β-expansions of real numbers, Acta Math. Acad. Sci. Hungar., 11, 401-416 (1960) · Zbl 0099.28103
[18] Rényi, A., Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hungar., 8, 477-493 (1957) · Zbl 0079.08901
[19] Sakarovitch, J., Description des monoïdes de type fini, E.I.K., 8/9, 417-434 (1981) · Zbl 0572.20037
[20] Zeckendorf, E., Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège, 3-4, 179-182 (1972) · Zbl 0252.10011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.