Sur les ensembles d'entiers reconnaissables
Journal de théorie des nombres de Bordeaux, Volume 10 (1998) no. 1, p. 65-84

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.

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.

@article{JTNB_1998__10_1_65_0,
     author = {Durand, Fabien},
     title = {Sur les ensembles d'entiers reconnaissables},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux I},
     volume = {10},
     number = {1},
     year = {1998},
     pages = {65-84},
     zbl = {1046.11500},
     mrnumber = {1827286},
     language = {fr},
     url = {http://www.numdam.org/item/JTNB_1998__10_1_65_0}
}
Durand, Fabien. Sur les ensembles d'entiers reconnaissables. Journal de théorie des nombres de Bordeaux, Volume 10 (1998) no. 1, pp. 65-84. http://www.numdam.org/item/JTNB_1998__10_1_65_0/

[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 0628.58024

[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 1029085 | Zbl 0695.10005

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

[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 0957.11015

[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 1318968 | Zbl 0804.11024

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

[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 614317 | Zbl 0472.10035

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

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

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

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

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

[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 1292734 | Zbl 0814.11015

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

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

[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 1637516

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

[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 1370990 | Zbl 0857.03003

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

[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 784265 | Zbl 0554.68053

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

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

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

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