Sur les ensembles d'entiers reconnaissables

Fabien Durand

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

  • Volume: 10, Issue: 1, page 65-84
  • ISSN: 1246-7405

Abstract

top
Let U and V be two Bertrand numeration systems, α and β be two multiplicatively independent β -numbers such that L ( U ) = L ( α ) and L ( V ) = L ( β ) , and E be a subset of ℕ . If E is both U -recognizable and V -recognizable then E is a finite union of arithmetic progressions.

How to cite

top

Durand, Fabien. "Sur les ensembles d'entiers reconnaissables." Journal de théorie des nombres de Bordeaux 10.1 (1998): 65-84. <http://eudml.org/doc/248164>.

@article{Durand1998,
abstract = {Soient $U$ et $V$ deux systèmes de numération de Bertrand, $\alpha $ et $\beta $ deux $\beta $-nombres multiplicativement indépendants tels que $L(U) = L(\alpha )$ et $L(V) = L(\beta )$, et $E$ un sous-ensemble de $\mathbb \{N\}$. Si $E$ est $U$-reconnaissable et $V$-reconnaissable alors $E$ est une réunion finie de progressions arithmétiques.},
author = {Durand, Fabien},
journal = {Journal de théorie des nombres de Bordeaux},
language = {fre},
number = {1},
pages = {65-84},
publisher = {Université Bordeaux I},
title = {Sur les ensembles d'entiers reconnaissables},
url = {http://eudml.org/doc/248164},
volume = {10},
year = {1998},
}

TY - JOUR
AU - Durand, Fabien
TI - Sur les ensembles d'entiers reconnaissables
JO - Journal de théorie des nombres de Bordeaux
PY - 1998
PB - Université Bordeaux I
VL - 10
IS - 1
SP - 65
EP - 84
AB - Soient $U$ et $V$ deux systèmes de numération de Bertrand, $\alpha $ et $\beta $ deux $\beta $-nombres multiplicativement indépendants tels que $L(U) = L(\alpha )$ et $L(V) = L(\beta )$, et $E$ un sous-ensemble de $\mathbb {N}$. Si $E$ est $U$-reconnaissable et $V$-reconnaissable alors $E$ est une réunion finie de progressions arithmétiques.
LA - fre
UR - http://eudml.org/doc/248164
ER -

References

top
  1. [Ber1] A. Bertrand-Mathis, 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
  2. [Ber3] A. Bertrand-Mathis, Comment écrire les nombres entiers dans une base qui n'est pas entière, Acta Math. Acad. Sci. Hungar.54 (1989), 237-241. Zbl0695.10005MR1029085
  3. [Bes] A. Bès, An extension of Cobham-Semënov theorem, preprint. Zbl0958.03025MR1782115
  4. [BH1] V. Bruyère and G. Hansel, Recognizable sets of numbers in nonstandard bases, Lecture Notes in Comput. Sci.911 (1995) 167-179. 
  5. [BH2] V. Bruyère and G. Hansel, Bertrand numeration systems and recognizability, à paraître dans Theo. Comp. Sci.. Zbl0957.11015
  6. [BHMV] V. Bruyère, G. Hansel, C. Michaux and R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belgian Math. Soc. Simon Stevin vol. 1 (1994) 191-238. Zbl0804.11024MR1318968
  7. [BP] V. Bruyère and F. Point, On the Cobham-Semënov theorem, Theory of Computing Systems30 (1997), 197-220. Zbl0870.68065MR1424937
  8. [CKMR] G. Christol, T. Kamae, M. Mendès-France et G. Rauzy, Suites Algébriques et Substitutions, Bull. Soc. Math. France108 (1980), 401-419. Zbl0472.10035MR614317
  9. [Co1] A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Syst. Theo.3 (1969), 186-192. Zbl0179.02501MR250789
  10. [Co2] A. Cobham, Uniform tag sequences, Math. Syst. Theo.6 (1972), 164-192. Zbl0253.02029MR457011
  11. [Du1] F. Durand, A characterization of substitutive sequences using return words, Disc. Math.179 (1998), 89-101. Zbl0895.68087MR1489074
  12. [Du2] F. Durand, A generalization of Cobham's theorem, à paraître dans Theory of Computing Systems. Zbl0895.68081
  13. [DHS] F. Durand, B. Host and C. Skau, Substitutions, Bratteli diagrams and dimension groups, à paraître dans Ergod. Th. & Dynam. Sys.. Zbl1044.46543
  14. [Ei] S. Eilenberg, Automata, Languages and Machines, Academic Press vol. A. 
  15. [Fa1] S. Fabre, Une généralisation du théorème de Cobham, Acta Arithmetica LXVII.3 (1994) 197-208. Zbl0814.11015MR1292734
  16. [Fa2] S. Fabre, Substitutions et β-systèmes de numération, Theo. Comp. Sc.137 (1995), 219-236. Zbl0872.11017
  17. [Fag1] I. Fagnot, Sur les facteurs des mots automatiques, à paraître dansTheo. Comp. Sci.. Zbl0983.68102
  18. [Fag2] I. Fagnot, Cobham's theorem and automaticity in non-standard bases, preprint. 
  19. [Ha1] G. Hansel, A propos d'un théorème de Cobham, Actes de la fête des mots, D. Perrin Ed., GRECO de programmation, Rouen (1982). 
  20. [Ha2] G. Hansel, Systèmes de numération indépendants et syndéticité, preprint. MR1637516
  21. [LM] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press (1995). Zbl1106.37301MR1369092
  22. [MV] C. Michaux and R. Villemaire, Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's theorem and Semenov's theorem, Annals of Pure and Applied Logic77 (1996), 251-277. Zbl0857.03003MR1370990
  23. [Mo] B. Mossé, Puissances de mots et reconnaissabilité des points fixes d'une substitution, Theo. Comp. Sci.99 (1992), 327-334. Zbl0763.68049MR1168468
  24. [Pan] J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, Lect. Notes in Comp. Sci.172 (1984), 380-389. Zbl0554.68053MR784265
  25. [Par] W. Parry, On the β-expansions of real numbers, Acta Math. Acad. Sci. Hungar11 (1960), 401-416. Zbl0099.28103
  26. [Qu] M. Queffélec, Substitution Dynamical Systems-Spectral Analysis, Lecture Notes in Math. vol.1294 (1987). Zbl0642.28013MR924156
  27. [Se] A.L. Semenov, The Presburger nature of predicates that are regular in two number systems, Siberian Math. J.18 (1977), 289-299. Zbl0411.03054MR450050
  28. [Sh] J. Shallit, Numeration systems, linear recurrences and regular sets, Theo. Comp. Sci.61 (1988), 1-16. Zbl0662.68052

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.