Book contents
- Frontmatter
- Contents
- FOREWORD
- 1 SEQUENCES OF LOW COMPLEXITY: AUTOMATIC AND STURMIAN SEQUENCES
- 2 SUBSTITUTION SUBSHIFTS AND BRATTELI DIAGRAMS
- 3 ALGEBRAIC ASPECTS OF SYMBOLIC DYNAMICS
- 4 DYNAMICS OF ℤd ACTIONS ON MARKOV SUBGROUPS
- 5 ASYMPTOTIC LAWS FOR SYMBOLIC DYNAMICAL SYSTEMS
- 6 ERGODIC THEORY AND DIOPHANTINE PROBLEMS
- 7 NUMBER REPRESENTATION AND FINITE AUTOMATA
- 8 A NOTE ON THE TOPOLOGICAL CLASSIFICATION OF LORENZ MAPS ON THE INTERVAL
7 - NUMBER REPRESENTATION AND FINITE AUTOMATA
Published online by Cambridge University Press: 05 August 2013
- Frontmatter
- Contents
- FOREWORD
- 1 SEQUENCES OF LOW COMPLEXITY: AUTOMATIC AND STURMIAN SEQUENCES
- 2 SUBSTITUTION SUBSHIFTS AND BRATTELI DIAGRAMS
- 3 ALGEBRAIC ASPECTS OF SYMBOLIC DYNAMICS
- 4 DYNAMICS OF ℤd ACTIONS ON MARKOV SUBGROUPS
- 5 ASYMPTOTIC LAWS FOR SYMBOLIC DYNAMICAL SYSTEMS
- 6 ERGODIC THEORY AND DIOPHANTINE PROBLEMS
- 7 NUMBER REPRESENTATION AND FINITE AUTOMATA
- 8 A NOTE ON THE TOPOLOGICAL CLASSIFICATION OF LORENZ MAPS ON THE INTERVAL
Summary
Christiane FROUGNY
Université Paris 8 and
CNRS, Laboratoire d'Informatique Algorithmique:
Fondements et Applications
Case 7014, 2 place Jussieu, 75251 Paris Cedex 05
France
In positional numeration systems, numbers are represented as finite or infinite strings of digits, and thus Symbolic Dynamics is a useful conceptual framework for the study of number representation. We use finite automata to modelize simple arithmetic operations like addition. In this chapter, we first recall some results on the usual representation of numbers to an integer base. Then we consider the case where the base is a real number but not an integer, the so-called beta-expansions. Finally, we treat of the representation of integers with respect to a sequence of integers, for instance the Fibonacci numbers.
Introduction
In this survey, numbers are seen as finite or infinite strings of digits from a finite set. This implies of course that several concepts from Symbolic Dynamics find an illustration in number representation. For instance, the set of base 2 expansions of real numbers from the interval [0, 1] is the one-sided full 2-shift. Number representation has a long and fascinating history; some of its developments can be found in the book of Knuth [28]. In particular, non-classical numeration systems like the Fibonacci numeration system are quite well known. In Computer Arithmetics, it is recognized that algorithmic possibilities depend on the representation of numbers. For instance, addition of two integers represented in the usual binary system with the digits 0 and 1, takes a time which is proportional to the size of the data.
- Type
- Chapter
- Information
- Topics in Symbolic Dynamics and Applications , pp. 207 - 228Publisher: Cambridge University PressPrint publication year: 2000
- 2
- Cited by