×

Properties and limits of recognition of sets of integers by countable automata. (Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables.) (English. French summary) Zbl 1211.68231

Summary: We study two families of sets of integers recognized by countable automata. The 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 given.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] B. Adamczewski et J. Cassaigne, Diophantine properties of real numbers generated by finite automata. Compositio Math. 142 (2006), 1351-1372. · Zbl 1134.11011
[2] J.-P. Allouche et J. Shallit, Automatic sequences. Theory, applications, generalizations. Cambridge University Press, 2003. · 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. · Zbl 0774.68072
[4] J.-P. Allouche et J. Shallit, The ring of k-regular sequences, II. Theor. Comp. Sci. 307 (2003), 3-29. · Zbl 1058.68066
[5] J.-M. Autebert, Langages algébriques. Etudes et recherche en informatique, Masson, 1987.
[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.
[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. · 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. · Zbl 0179.02501
[10] A. Cobham, Uniform-tag sequences. Math. Syst. Theory 6 (1972), 164-192. · Zbl 0253.02029
[11] D. Caucal, On the regular structure of prefix rewriting. Theor. Comp. Sci. 106 (1992), 61-86. · Zbl 0780.68077
[12] D. Caucal, On infinite transition graphs having a decidable monadic theory. Theor. Comp. Sci. 290 (2003), 79-115. · Zbl 1019.68066
[13] S. Eilenberg, Automata, languages and machines, Vol. A. Academic Press, 1974. · Zbl 0317.94045
[14] S. Ferenczi, Substitutions on an infinite alphabet. Ann. Inst. Fourier 56 nº7 (2006), 2315-2343. · 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. · 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. · Zbl 1041.11008
[17] J. Hartmanis et H. Shank, On the recognition of primes by automata. J. Assoc. Comput. Mach. 15 (1968), 382-389. · 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. · Zbl 1121.68090
[19] M. Le Gonidec, Drunken man infinite words complexity. RAIRO-Theor. Inf. Appl. 42 (2008), 599-613. · 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. · Zbl 1147.11016
[21] M. Minsky et S. Papert, Unrecognizable sets of numbers. J. Assoc. Comput. Mach. 13 (1966), 281-286. · 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. · Zbl 0605.03005
[23] M. Rigo, Generalization of automatic sequences for numeration systems on a regular language. Theor. Comp. Sci. 244 (2000), 271-281. · Zbl 0945.68105
[24] R. W. Ritchie, Finite automata and the set of squares. J. Assoc. Comput. Mach. 10 (1963), 528-531. · 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. · Zbl 0165.02204
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.