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.