A full characterization of Bertrand numeration systems

[en] Among all positional numeration systems, the widely studied Bertrand numeration systems are defined by a simple criterion in terms of their numeration languages. In 1989, Bertrand-Mathis characterized them via representations in a real base β. However, the given condition turns out to be not necessary. Hence, the goal of this paper is to provide a correction of Bertrand-Mathis' result. The main difference arises when β is a Parry number, in which case two associated Bertrand numeration systems are derived. Along the way, we define a non-canonical β-shift and study its properties analogously to those of the usual canonical one.

Disciplines :

Mathematics

Author, co-author :

Charlier, Emilie ; Université de Liège - ULiège > Mathematics

Cisternino, Célia ; Université de Liège - ULiège > Mathematics

Stipulanti, Manon ; Université de Liège - ULiège > Mathematics

Language :

English

Title :

A full characterization of Bertrand numeration systems

Publication date :

2022

Event name :

Developments in Language Theory

Event date :

du 9 mai 2022 au 13 mai 2022

Audience :

International

Journal title :

Lecture Notes in Computer Science

ISSN :

0302-9743

eISSN :

1611-3349

Publisher :

Springer, Heidelberg, Germany

Volume :

13257

Pages :

102-114

Peer reviewed :

Peer reviewed

Available on ORBi :

since 21 March 2022

Statistics

Number of views

50 (11 by ULiège)

Number of downloads

40 (6 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Bertrand-Mathis, A.: Développement en base θ; répartition modulo un de la suite (xθn )n≥0; langages codés et θ-shift. Bull. Soc. Math. France 114(3), 271–323 (1986)
Bertrand-Mathis, A.: Comment écrire les nombres entiers dans une base qui n’est pas entière. Acta Math. Hungar. 54(3–4), 237–241 (1989)
Bruyère, V., Hansel, G.: Bertrand numeration systems and recognizability. Theoret. Comput. Sci. 181(1), 17–43 (1997)
Charlier, E., Rampersad, N., Rigo, M., Waxweiler, L.: The minimal automaton recognizing mN in a linear numeration system. Integers 11B, A4, 24 (2011)
Dajani, K., Kraaikamp, C.: Ergodic Theory of Numbers, Carus Mathematical Monographs, vol. 29. Mathematical Association of America, Washington, DC (2002)
Feller, W.: An Introduction To Probability Theory and Its Applications, vol. 1, 2nd edn. John Wiley and Sons Inc.; Chapman and Hall Ltd., New York, London (1957)
Frougny, C., Solomyak, B.: On representation of integers in linear numeration systems. In: Ergodic theory of Zd actions, London Mathematical Society Lecture Note Series, vol. 228, pp. 345–368. Cambridge University Press, Cambridge (1996)
Hollander, M.: Greedy numeration systems and regularity. Theory Comput. Syst. 31(2), 111–133 (1998)
Loraud, N.: β-shift, systèmes de numération et automates. J. Théor. Nombres Bordeaux 7(2), 473–498 (1995)
Lothaire, M.: Algebraic combinatorics on Words, Encyclopedia of Mathematics and Its Applications, vol. 90. Cambridge University Press, Cambridge (2002)
Massuir, A., Peltomäki, J., Rigo, M.: Automatic sequences based on Parry or Bertrand numeration systems. Adv. Appl. Math. 108, 11–30 (2019)
Parry, W.: On the β-expansions of real numbers. Acta Math. Acad. Sci. Hungar. 11, 401–416 (1960)
Point, F.: On decidable extensions of Presburger arithmetic: from A. Bertrand numeration systems to Pisot numbers. J. Symbolic Logic 65(3), 1347–1374 (2000)
Rényi, A.: Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hungar. 8, 477–493 (1957)
Schmidt, K.: On periodic expansions of Pisot numbers and Salem numbers. Bull. London Math. Soc. 12(4), 269–278 (1980)
Shallit, J.: Numeration systems, linear recurrences, and regular sets. Inform. Comput. 113(2), 331–347 (1994)
Stipulanti, M.: Convergence of Pascal-like triangles in Parry-Bertrand numeration systems. Theoret. Comput. Sci. 758, 42–60 (2019)
Walters, P.: An Introduction to Ergodic Theory, Graduate Texts in Mathematics, vol. 79. Springer-Verlag, New York, Berlin (1982). https://link.springer. com/book/9780387951522
Zeckendorf, E.: Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. Roy. Sci. Liège 41, 179–182 (1972)