×

zbMATH — the first resource for mathematics

Representations of numbers and finite automata. (English) Zbl 0776.11005
This paper is an extended English version with detailed proofs of a paper already reviewed here [Theor. Comput. Sci. 94, 223-236 (1992; Zbl 0751.11008)].
The author obtained in a recent paper with D. Berend [to appear in Math. Syst. Theory] the following nice result (one way is contained in the paper under review): The normalization in base \(\theta\) is computable by a finite automaton if and only if \(\theta\) is a Pisot number. Note that the author also obtained new results in a recent preprint with Solomyak, where she studies the normalization of integers in a linear numeration system associated to a Pisot number.

MSC:
11A67 Other number representations
68Q45 Formal languages and automata
54H20 Topological dynamics (MSC2010)
11B85 Automata sequences
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. Avizienis, Signed-digit number representations for fast parallel arithmetic.IRE Trans. Electron. Comput. 10, 1961, 389-400. · doi:10.1109/TEC.1961.5219227
[2] J. Berstel,Transductions and Context-free Languages. Teubner, Stuttgart, 1979. · Zbl 0424.68040
[3] A. Bertrand-Mathis, Répartition modulo un des suites exponentielles et systémes dynamiques symboliques. Thèse d’Etat, Université Bordeaux 1, 1986.
[4] J. P. Bézivin, Personal communication, 1989.
[5] F. Blanchard, ?-expansions and symbolic dynamics.Theoret. Comput. Sci. 65, 1989, 131-141. · Zbl 0682.68081 · doi:10.1016/0304-3975(89)90038-8
[6] A. Brauer, On algebraic equations with all but one root in the interior of the unit circle.Math. Nachr. 4, 1951, 250-257. · Zbl 0042.01501
[7] S. Eilenberg,Automata, Languages and Machines, Vol. A, Academic Press, New York, 1974. · Zbl 0317.94045
[8] A. S. Fraenkel, Systems of numeration.Amer. Math. Monthly 92(2), 1985, 105-114. · Zbl 0568.10005 · doi:10.2307/2322638
[9] Ch. Frougny, Linear numeration systems of order two.Inform. Comput. 77, 1988, 233-259. · Zbl 0648.68066 · doi:10.1016/0890-5401(88)90050-8
[10] Ch. Frougny, Linear numeration systems, ?-developments and finite automata.Proceedings of STACS 89, Lecture Notes in Computer Science, Vol. 349, Springer-Verlag, Berlin, 1989, pp. 144-155.
[11] Ch. Frougny, Systémes de numération linéaires et automates finis. Thèse d’Etat, Université Paris 7, Rapport LITP 89-69, 1989.
[12] Ch. Frougny and J. Sakarovitch, Rational relations with bounded delay.Proceedings of STACS 91, Lecture Notes in Computer Science, Vol. 480, Springer-Verlag, Berlin, 1991, pp. 50-63. · Zbl 0773.68045
[13] D. E. Knuth,The Art of Computer Programming, Vols. 1-3. Addison-Wesley, Reading, MA, 1975.
[14] D. Lind, The entropies of topological Markov shifts and a related class of algebraic integers.Ergodic Theory Dynamical Systems 4, 1984, 283-300. · Zbl 0546.58035
[15] W. Parry, On the ?-expansions of real numbers.Acta Math. Acad. Sci. Hungar. 11, 1960, 401-416. · Zbl 0099.28103 · doi:10.1007/BF02020954
[16] A. Pethö and R. Tichy, On digit expansions with respect to linear recurrences.J. Number Theory 33, 1989, 243-256. · Zbl 0676.10010 · doi:10.1016/0022-314X(89)90011-5
[17] G. Rauzy, Sur la latitude d’un développement en base non entière. To appear.
[18] A. Rényi, Representations for real numbers and their ergodic properties.Acta Math. Acad. Sci. Hungar. 8, 1957, 477-493. · Zbl 0079.08901 · doi:10.1007/BF02020331
[19] E. Zeckendorf, 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, 1972, 179-182. · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.