Sur les ensembles d'entiers reconnaissables

Fabien Durand

Fabien Durand

Journal de théorie des nombres de Bordeaux, Tome 10 (1998) no. 1, pp. 65-84.

Résumé
Abstract

Soient $U$ et $V$ deux systèmes de numération de Bertrand, $α$ et $β$ deux $β$ -nombres multiplicativement indépendants tels que $L (U) = L (α)$ et $L (V) = L (β)$ , et $E$ un sous-ensemble de $ℕ$ . Si $E$ est $U$ -reconnaissable et $V$ -reconnaissable alors $E$ est une réunion finie de progressions arithmétiques.

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.

MR Zbl

@article{JTNB_1998__10_1_65_0,
     author = {Fabien Durand},
     title = {Sur les ensembles d'entiers reconnaissables},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {65--84},
     publisher = {Universit\'e Bordeaux I},
     volume = {10},
     number = {1},
     year = {1998},
     zbl = {1046.11500},
     mrnumber = {1827286},
     language = {fr},
     url = {https://jtnb.centre-mersenne.org/item/JTNB_1998__10_1_65_0/}
}

TY  - JOUR
AU  - Fabien Durand
TI  - Sur les ensembles d'entiers reconnaissables
JO  - Journal de théorie des nombres de Bordeaux
PY  - 1998
SP  - 65
EP  - 84
VL  - 10
IS  - 1
PB  - Université Bordeaux I
UR  - https://jtnb.centre-mersenne.org/item/JTNB_1998__10_1_65_0/
LA  - fr
ID  - JTNB_1998__10_1_65_0
ER  -

%0 Journal Article
%A Fabien Durand
%T Sur les ensembles d'entiers reconnaissables
%J Journal de théorie des nombres de Bordeaux
%D 1998
%P 65-84
%V 10
%N 1
%I Université Bordeaux I
%U https://jtnb.centre-mersenne.org/item/JTNB_1998__10_1_65_0/
%G fr
%F JTNB_1998__10_1_65_0

Fabien Durand. Sur les ensembles d'entiers reconnaissables. Journal de théorie des nombres de Bordeaux, Tome 10 (1998) no. 1, pp. 65-84. https://jtnb.centre-mersenne.org/item/JTNB_1998__10_1_65_0/

Bibliographie
Cité par

[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. France 114 (1986), 271-323. | Numdam | Zbl

[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. | MR | Zbl

[Bes] A. Bès, An extension of Cobham-Semënov theorem, preprint. | MR

[BH1] V. Bruyère and G. Hansel, Recognizable sets of numbers in nonstandard bases, Lecture Notes in Comput. Sci. 911 (1995) 167-179.

[BH2] V. Bruyère and G. Hansel, Bertrand numeration systems and recognizability, à paraître dans Theo. Comp. Sci.. | Zbl

[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. | MR | Zbl

[BP] V. Bruyère and F. Point, On the Cobham-Semënov theorem, Theory of Computing Systems 30 (1997), 197-220. | MR | Zbl

[CKMR] G. Christol, T. Kamae, M. Mendès-France et G. Rauzy, Suites Algébriques et Substitutions, Bull. Soc. Math. France 108 (1980), 401-419. | Numdam | MR | Zbl

[Co1] A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Syst. Theo. 3 (1969), 186-192. | MR | Zbl

[Co2] A. Cobham, Uniform tag sequences, Math. Syst. Theo. 6 (1972), 164-192. | MR | Zbl

[Du1] F. Durand, A characterization of substitutive sequences using return words, Disc. Math. 179 (1998), 89-101. | MR | Zbl

[Du2] F. Durand, A generalization of Cobham's theorem, à paraître dans Theory of Computing Systems. | Zbl

[DHS] F. Durand, B. Host and C. Skau, Substitutions, Bratteli diagrams and dimension groups, à paraître dans Ergod. Th. & Dynam. Sys.. | Zbl

[Ei] S. Eilenberg, Automata, Languages and Machines, Academic Press vol. A.

[Fa1] S. Fabre, Une généralisation du théorème de Cobham, Acta Arithmetica LXVII.3 (1994) 197-208. | MR | Zbl

[Fa2] S. Fabre, Substitutions et β-systèmes de numération, Theo. Comp. Sc. 137 (1995), 219-236. | Zbl

[Fag1] I. Fagnot, Sur les facteurs des mots automatiques, à paraître dans Theo. Comp. Sci.. | Zbl

[Fag2] I. Fagnot, Cobham's theorem and automaticity in non-standard bases, preprint.

[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).

[Ha2] G. Hansel, Systèmes de numération indépendants et syndéticité, preprint. | MR

[LM] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press (1995). | MR | Zbl

[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 Logic 77 (1996), 251-277. | MR | Zbl

[Mo] B. Mossé, Puissances de mots et reconnaissabilité des points fixes d'une substitution, Theo. Comp. Sci. 99 (1992), 327-334. | MR | Zbl

[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. | MR | Zbl

[Par] W. Parry, On the β-expansions of real numbers, Acta Math. Acad. Sci. Hungar 11 (1960), 401-416. | Zbl

[Qu] M. Queffélec, Substitution Dynamical Systems-Spectral Analysis, Lecture Notes in Math. vol.1294 (1987). | MR | Zbl

[Se] A.L. Semenov, The Presburger nature of predicates that are regular in two number systems, Siberian Math. J.18 (1977), 289-299. | MR | Zbl

[Sh] J. Shallit, Numeration systems, linear recurrences and regular sets, Theo. Comp. Sci. 61 (1988), 1-16. | Zbl