Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables
Journal de théorie des nombres de Bordeaux, Tome 22 (2010) no. 2, pp. 307-338.

Nous étudions dans cet article deux familles d’ensembles d’entiers reconnaissables par des automates finis ou dénombrables. Les résultats concernant ces deux notions de reconnaissabilité qui sont présentés ici étendent de manière naturelle les résultats structurels usuels de la famille des ensembles k-reconnaissables. Le cas particulier de l’ensemble des nombres premiers est également abordé.

Properties and limits of recognition of sets of integers by countable automata We study two families of sets of integers recognized by countable automata. Presented results on these two recognition notions naturally extend usual structural results about the family of k-recognizable sets. The particular case of the set of prime numbers is also detailed.

DOI : 10.5802/jtnb.717
Cassaigne, Julien 1 ; Le Gonidec, Marion 2

1 Institut de mathématiques de Luminy case 907 13288 Marseille Cedex 9, France
2 Université du Sud - Toulon - Var Avenue de l’Université - BP20132 83957 La Garde Cedex, France
@article{JTNB_2010__22_2_307_0,
     author = {Cassaigne, Julien and Le Gonidec, Marion},
     title = {Propri\'et\'es et limites de la reconnaissance d{\textquoteright}ensembles d{\textquoteright}entiers par automates d\'enombrables},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {307--338},
     publisher = {Universit\'e Bordeaux 1},
     volume = {22},
     number = {2},
     year = {2010},
     doi = {10.5802/jtnb.717},
     zbl = {1211.68231},
     mrnumber = {2769064},
     language = {fr},
     url = {http://archive.numdam.org/articles/10.5802/jtnb.717/}
}
TY  - JOUR
AU  - Cassaigne, Julien
AU  - Le Gonidec, Marion
TI  - Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2010
SP  - 307
EP  - 338
VL  - 22
IS  - 2
PB  - Université Bordeaux 1
UR  - http://archive.numdam.org/articles/10.5802/jtnb.717/
DO  - 10.5802/jtnb.717
LA  - fr
ID  - JTNB_2010__22_2_307_0
ER  - 
%0 Journal Article
%A Cassaigne, Julien
%A Le Gonidec, Marion
%T Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables
%J Journal de théorie des nombres de Bordeaux
%D 2010
%P 307-338
%V 22
%N 2
%I Université Bordeaux 1
%U http://archive.numdam.org/articles/10.5802/jtnb.717/
%R 10.5802/jtnb.717
%G fr
%F JTNB_2010__22_2_307_0
Cassaigne, Julien; Le Gonidec, Marion. Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables. Journal de théorie des nombres de Bordeaux, Tome 22 (2010) no. 2, pp. 307-338. doi : 10.5802/jtnb.717. http://archive.numdam.org/articles/10.5802/jtnb.717/

[1] B. Adamczewski et J. Cassaigne, Diophantine properties of real numbers generated by finite automata. Compositio Math. 142 (2006), 1351–1372. | MR | Zbl

[2] J.-P. Allouche et J. Shallit, Automatic sequences. Theory, applications, generalizations. Cambridge University Press, 2003. | MR | Zbl

[3] J.-P. Allouche et J. Shallit, The ring of k-regular sequences. Theor. Comp. Sci. 98 (1992), nº2, 163–197. | MR | Zbl

[4] J.-P. Allouche et J. Shallit, The ring of k-regular sequences, II. Theor. Comp. Sci. 307 (2003), 3–29. | MR | Zbl

[5] J.-M. Autebert, Langages algébriques. Etudes et recherche en informatique, Masson, 1987. | MR

[6] J.-M. Autebert, J. Berstel et L. Boasson, Context-free languages and pushdown automata. In Handbook of formal languages, Vol. 1, Springer (1997), 111–174. | MR

[7] J. Berstel, On Sets of Numbers Recognized by Push-Down Automata. IEEE Conference record of 13th Annual Symposium of Foundations of Computer Sciences (FOCS’72) (1972), 200–206.

[8] J. Berstel, Sur la densité asymptotique de langages formels. Proceedings of International Colloquium on Automata, Languages and Programming (ICALP’72) (1973), 345–358. | MR | Zbl

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

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

[11] D. Caucal, On the regular structure of prefix rewriting. Theor. Comp. Sci. 106 (1992), 61–86. | MR | Zbl

[12] D. Caucal, On infinite transition graphs having a decidable monadic theory. Theor. Comp. Sci. 290 (2003), 79–115. | MR | Zbl

[13] S. Eilenberg, Automata, languages and machines, Vol. A. Academic Press, 1974. | MR | Zbl

[14] S. Ferenczi, Substitutions on an infinite alphabet. Ann. Inst. Fourier 56 nº7 (2006), 2315–2343. | Numdam | MR | Zbl

[15] C. Fouvry et C. Mauduit, Sur les entiers dont la somme des chiffres est moyenne. J. Number Theory 114 nº1 (2005), 135–152. | MR | Zbl

[16] C. Frougny et B. Solomyak, On the context-freeness of the θ-expansions of the integers. Internat. J. Algebra Comput. 9 nº3-4 (1999), 347–350. | MR | Zbl

[17] J. Hartmanis et H. Shank, On the recognition of primes by automata. J. Assoc. Comput. Mach. 15 (1968), 382–389. | MR | Zbl

[18] M. Le Gonidec. Sur la complexité des mots infinis engendrés par des q-automates dénombrables. Ann. Inst. Fourier 56 nº7 (2006), 2463–2491. | Numdam | MR | Zbl

[19] M. Le Gonidec, Drunken man infinite words complexity. RAIRO-Theor. Inf. Appl. 42 (2008), 599–613. | Numdam | MR | Zbl

[20] C. Mauduit, Propriétés arithmétiques des substitutions et automates infinis. Ann. Inst. Fourier 56 nº7 (2006), 2525–2549. | Numdam | MR | Zbl

[21] M. Minsky et S. Papert, Unrecognizable sets of numbers. J. Assoc. Comput. Mach. 13 (1966), 281–286. | MR | Zbl

[22] D. Muller et P. Shupp, The theory of ends, pushdown automata and second-order logic. Theor. Comp. Sci. 37 (1985), 51–75. | MR | Zbl

[23] M. Rigo, Generalization of automatic sequences for numeration systems on a regular language. Theor. Comp. Sci. 244 (2000), 271–281. | MR | Zbl

[24] R. W. Ritchie, Finite automata and the set of squares. J. Assoc. Comput. Mach. 10 (1963), 528–531. | MR | Zbl

[25] J. Sakarovitch, Élements de théorie des automates. Vuibert, 2003. | Zbl

[26] M.-P. Schützenberger, A remark on acceptable sets of numbers. J. Assoc. Comput. Mach. 15 (1968), 300–303. | MR | Zbl

Cité par Sources :