β -shift, systèmes de numération et automates

Nathalie Loraud

Journal de théorie des nombres de Bordeaux (1995)

  • Volume: 7, Issue: 2, page 473-498
  • ISSN: 1246-7405

Abstract

top
In this note we prove that the language of a numeration system is the language of a β -shift under some assumptions on the basis. We deduce from this result a partial answer to the question when the language of a numeration system is regular. Moreover, we give a characterization of the arithmetico-geometric sequences and the mixed radix sequences that are basis of a numeration system for which the language is regular. Finally, we study the Ostrowski systems of numeration and give another proof of the result of J. Shallit : the Ostrowski systems having a regular langage are exactly the ones associated to a quadratic number.

How to cite

top

Loraud, Nathalie. "$\beta $-shift, systèmes de numération et automates." Journal de théorie des nombres de Bordeaux 7.2 (1995): 473-498. <http://eudml.org/doc/247644>.

@article{Loraud1995,
author = {Loraud, Nathalie},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {-shift; automata; numeration systems; formal languages; linear recurrences; regularity; arithmetico-geometric sequences; mixed radix sequences; Ostrowski systems; continued fraction expansions; regular language; quadratic irrational; numeration system},
language = {fre},
number = {2},
pages = {473-498},
publisher = {Université Bordeaux I},
title = {$\beta $-shift, systèmes de numération et automates},
url = {http://eudml.org/doc/247644},
volume = {7},
year = {1995},
}

TY - JOUR
AU - Loraud, Nathalie
TI - $\beta $-shift, systèmes de numération et automates
JO - Journal de théorie des nombres de Bordeaux
PY - 1995
PB - Université Bordeaux I
VL - 7
IS - 2
SP - 473
EP - 498
LA - fre
KW - -shift; automata; numeration systems; formal languages; linear recurrences; regularity; arithmetico-geometric sequences; mixed radix sequences; Ostrowski systems; continued fraction expansions; regular language; quadratic irrational; numeration system
UR - http://eudml.org/doc/247644
ER -

References

top
  1. [Be 1]: A. Bertrand, Comment écrire les nombres entiers dans une base qui n'est pas entière. à paraître dansActa. Math. Acad. Sci. Hungar. Zbl0695.10005
  2. [Be 2]: A. Bertrand, Questions diverses relatives aux systèmes codés: applications au θ-shift. Preprint 
  3. [Be 3]: A. Bertrand, Nombres de Perron et problèmes de rationnalité. S. M. F. (1991), 198—200. Zbl0766.11043
  4. [Be 4]: A. Bertrand, Le θ-shift sans peine. en préparation. 
  5. [Be 5]: A. Bertrand, Développement en base θ, répartition modulo un de la suite (xθn) n≽0, langages codés et θ-shift. Bull. Soc. math. France114 (1986), 271-323. Zbl0628.58024
  6. [Bl]: F. Blanchard, β-expansions and symbolic dynamics. Theoret. Comput. Sci.65 (1989), 131-141. Zbl0682.68081
  7. [Br]: A. Brauer, On algebraic equations with all but one root in the interior of the unit circle. Math. Nachr.4 (1951), 250-257. Zbl0042.01501MR41975
  8. [Co]: A. Cobham, Uniform tag sequences. Math. Syst. Theory6 (1972), 164-192. Zbl0253.02029MR457011
  9. [Fr 1]: A.S. Fraenkel, Systems of numeration. Amer. Math. Monthly92 (1985), 105-114. Zbl0568.10005MR777556
  10. [Fr 2]: A.S. Fraenkel, The use and usefulness of numeration systems. Inform. and Comput.81 (1989), 46-61. Zbl0672.10008MR992303
  11. [Fro 1]: C. Frougny, Representations of numbers and finite automata. Math. Syst. Theory25 (1992), 37-60. Zbl0776.11005MR1139094
  12. [Fro 2]: C. Frougny, Linear Numeration Systems of Order Two. Inform. & Comput.77 (1988), 233-259. Zbl0648.68066MR942576
  13. [Fro 3]: C. Frougny, Systèmes de numération linéaires et θ-représentations. Theoret. Comput. Sci.94 (1992), 223—236. Zbl0751.11008
  14. [F-So]: C. Frougny, B. Solomyak, Finite β-expansions. Ergod. Th. & Dynam. Sys.12 (1992), 713-723. Zbl0814.68065
  15. [G-L-T]: P.J. Grabner, P. Liardet et R.F. Tichy, Odometers and systems of numerations. Acta Arith. to appear. Zbl0822.11008MR1322556
  16. [G-T 1]: P.J. Grabner, R.F. Tichy, Contributions to Digit Expansions with Respect to Linear Recurrences. J. Number Th.36 (1990), 160-169. Zbl0711.11004MR1072462
  17. [G-T 2]: P.J. Grabner, R.F. Tichy, α-expansions, Linear recurrences and the Sum-of-Digits Function. Manuscripta Math.70 (1991), 311-324. Zbl0725.11005
  18. [I-T]: S. Ito and Y. Takahashi, Markov subshifts and realization of β-expansions. J. Math. Soc. Japan261 (1974), 33—55. Zbl0269.28006
  19. [Li]: D. Lind, The entropies of topological Markov shifts and a related class of algebraic integers. Ergod. Th. &Dynam. Sys.4 (1984), 283-300. Zbl0546.58035MR766106
  20. [L-S]: J. Shallit, H.W. Lenstra, Continued fractions and linear recurrences. Math. Comp.61 (1993), 351-354. Zbl0797.11006MR1192972
  21. [Os]: A. Ostrowski, Bemerkungen zur Theorie der Diophantishen Approximationene. Abh. Math. Sem. Hamburg1 (1922), 77-98. JFM48.0185.01
  22. [Pa]: W. Parry, On the β-expansions of real numbers. Acta Math. Acad. Sci. Hungar.11 (1960), 401-416. Zbl0099.28103
  23. [P-T]: A. Pethö, R.F. Tichy, On Digit Expansions with Respect to Linear Recurrences. J. Number Th.33 (1989), 243-256. Zbl0676.10010MR1034204
  24. [Re]: A. Reyi, Representations for real numbers and their ergodic properties. Acta Math. Ac. Sci. Hungar.8 (1957), 477-493. Zbl0079.08901MR97374
  25. [Sc]: K. Schmidt, On periodic expansions of Pisot numbers and Salem numbers. Bull. London Math. Soc.12 (1980), 269-278. Zbl0494.10040MR576976
  26. [Sh 1]: J. Shallit, A generalization of automatic sequences. Theoret. Comput. Sci.61 (1988), 1-16. Zbl0662.68052MR974766
  27. [Sh 2]: J. Shallit, Numeration Systems, Linear Recurrences, and Regular Sets. Inform. and comput. to appear Zbl0810.11006MR1285236

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.