staple
With cedram.org

Search the site

Table of contents for this issue | Previous article | Next article
Julien Cassaigne; Marion Le Gonidec
Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables
Journal de théorie des nombres de Bordeaux, 22 no. 2 (2010), p. 307-338, doi: 10.5802/jtnb.717
Article PDF | Reviews MR 2769064 | Zbl 1211.68231

Résumé - Abstract

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.

Bibliography

[1] B. Adamczewski et J. Cassaigne, Diophantine properties of real numbers generated by finite automata. Compositio Math. 142 (2006), 1351–1372.  MR 2278750 |  Zbl 1134.11011
[2] J.-P. Allouche et J. Shallit, Automatic sequences. Theory, applications, generalizations. Cambridge University Press, 2003.  MR 1997038 |  Zbl 1086.11015
[3] J.-P. Allouche et J. Shallit, The ring of k-regular sequences. Theor. Comp. Sci. 98 (1992), nº2, 163–197.  MR 1166363 |  Zbl 0774.68072
[4] J.-P. Allouche et J. Shallit, The ring of k-regular sequences, II. Theor. Comp. Sci. 307 (2003), 3–29.  MR 2014728 |  Zbl 1058.68066
[5] J.-M. Autebert, Langages algébriques. Etudes et recherche en informatique, Masson, 1987.  MR 888601
[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 1469995
[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 386351 |  Zbl 0263.68043
[9] A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata. Math. Syst. Theory 3 (1969), 186–192.  MR 250789 |  Zbl 0179.02501
[10] A. Cobham, Uniform-tag sequences. Math. Syst. Theory 6 (1972), 164–192.  MR 457011 |  Zbl 0253.02029
[11] D. Caucal, On the regular structure of prefix rewriting. Theor. Comp. Sci. 106 (1992), 61–86.  MR 1193533 |  Zbl 0780.68077
[12] D. Caucal, On infinite transition graphs having a decidable monadic theory. Theor. Comp. Sci. 290 (2003), 79–115.  MR 1935687 |  Zbl 1019.68066
[13] S. Eilenberg, Automata, languages and machines, Vol. A. Academic Press, 1974.  MR 530382 |  Zbl 0317.94045
[14] S. Ferenczi, Substitutions on an infinite alphabet. Ann. Inst. Fourier 56 nº7 (2006), 2315–2343. Cedram |  MR 2290783 |  Zbl 1147.37007
[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 2163909 |  Zbl 1084.11045
[16] C. Frougny et B. Solomyak, On the context-freeness of the $\theta $-expansions of the integers. Internat. J. Algebra Comput. 9 nº3-4 (1999), 347–350.  MR 1723472 |  Zbl 1041.11008
[17] J. Hartmanis et H. Shank, On the recognition of primes by automata. J. Assoc. Comput. Mach. 15 (1968), 382–389.  MR 235916 |  Zbl 0164.05201
[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. Cedram |  MR 2290787 |  Zbl 1121.68090
[19] M. Le Gonidec, Drunken man infinite words complexity. RAIRO-Theor. Inf. Appl. 42 (2008), 599–613. Numdam |  MR 2434037 |  Zbl 1188.68217
[20] C. Mauduit, Propriétés arithmétiques des substitutions et automates infinis. Ann. Inst. Fourier 56 nº7 (2006), 2525–2549. Cedram |  MR 2290789 |  Zbl 1147.11016
[21] M. Minsky et S. Papert, Unrecognizable sets of numbers. J. Assoc. Comput. Mach. 13 (1966), 281–286.  MR 207481 |  Zbl 0166.00601
[22] D. Muller et P. Shupp, The theory of ends, pushdown automata and second-order logic. Theor. Comp. Sci. 37 (1985), 51–75.  MR 796313 |  Zbl 0605.03005
[23] M. Rigo, Generalization of automatic sequences for numeration systems on a regular language. Theor. Comp. Sci. 244 (2000), 271–281.  MR 1774400 |  Zbl 0945.68105
[24] R. W. Ritchie, Finite automata and the set of squares. J. Assoc. Comput. Mach. 10 (1963), 528–531.  MR 167374 |  Zbl 0118.12601
[25] J. Sakarovitch, Élements de théorie des automates. Vuibert, 2003.  Zbl 1178.68002
[26] M.-P. Schützenberger, A remark on acceptable sets of numbers. J. Assoc. Comput. Mach. 15 (1968), 300–303.  MR 238634 |  Zbl 0165.02204