Substitutions, coding prescriptions and integer representation

About the paper

language English
published in Journal of Number Theory 190 (2018)
pages 367 to 393
DOI 10.1016/j.jnt.2018.03.003
supported by FWF, project P28991-N35

Abstract

Coding prescriptions are combinatorial objects linked to a substitution, that is a morphism of the free monoid. Originally they have been introduced in order to code the induced symbolic dynamical system. In the present article we are interested in coding prescriptions of compositions and powers of substitutions. This will provide a very general framework for representing integers. We will study the properties and find several relations with well-known systems of integer numeration.

References

  1. J-.M. Dumont, A. Thomas, Systèmes de numération et fonctions fractales relatifs aux substitutions, Theor. Comput. Sci., 65 (1989), 153—169.
  2. J-.M. Dumont, A. Thomas, Digital sum problems and substitutions on a finite alphabet, J. Number Theory, 39 (1991), 351—366.
  3. P. Grabner, R. Tichy, Contributions to digit expansions with respect to linear recurrences, J. Number Theory, 36 (1990), 160—169.
  4. D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams, Addison-Wesley Professional, 12th~ed., 2009.
  5. A. Pethő, R. F. Tichy, On digit expansions with respect to linear recurrences, J. Number Theory, 33 (1989), 243—256.
  6. M. Queffélec, Substitution dynamical systems. Spectral analysis. 2nd ed., Lecture Notes in Mathematics 1294. Dordrecht: Springer. xv, 351 p., 2010.
  7. G. Rauzy, Nombres algébriques et substitutions, Bull. Soc. Math. France, 110 (1982), 147—178.
  8. P. Surer, Coding of substitution dynamical systems as shifts of finite type, Ergodic Theory Dyn. Syst., 36 (2016), 944—972.
  9. E. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. R. Sci. Liège, 41 (1972), 179—182.

Links

Journal of Number Theory
Austrian Science Foundation (FWF)
Homepage of the project P28991