Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables

Julien Cassaigne[1]; Marion Le Gonidec[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

Journal de Théorie des Nombres de Bordeaux (2010)

  • Volume: 22, Issue: 2, page 307-338
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

Cassaigne, Julien, and 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 22.2 (2010): 307-338. <http://eudml.org/doc/116405>.

@article{Cassaigne2010,
abstract = {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é.},
affiliation = {Institut de mathématiques de Luminy case 907 13288 Marseille Cedex 9, France; Université du Sud - Toulon - Var Avenue de l’Université - BP20132 83957 La Garde Cedex, France},
author = {Cassaigne, Julien, Le Gonidec, Marion},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {sets of integers; countable automata; -recognizable sets},
language = {fre},
number = {2},
pages = {307-338},
publisher = {Université Bordeaux 1},
title = {Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables},
url = {http://eudml.org/doc/116405},
volume = {22},
year = {2010},
}

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
PB - Université Bordeaux 1
VL - 22
IS - 2
SP - 307
EP - 338
AB - 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é.
LA - fre
KW - sets of integers; countable automata; -recognizable sets
UR - http://eudml.org/doc/116405
ER -

References

top
  1. B. Adamczewski et J. Cassaigne, Diophantine properties of real numbers generated by finite automata. Compositio Math. 142 (2006), 1351–1372. Zbl1134.11011MR2278750
  2. J.-P. Allouche et J. Shallit, Automatic sequences. Theory, applications, generalizations. Cambridge University Press, 2003. Zbl1086.11015MR1997038
  3. J.-P. Allouche et J. Shallit, The ring of k-regular sequences. Theor. Comp. Sci. 98 (1992), nº2, 163–197. Zbl0774.68072MR1166363
  4. J.-P. Allouche et J. Shallit, The ring of k-regular sequences, II. Theor. Comp. Sci. 307 (2003), 3–29. Zbl1058.68066MR2014728
  5. J.-M. Autebert, Langages algébriques. Etudes et recherche en informatique, Masson, 1987. MR888601
  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. MR1469995
  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. Zbl0263.68043MR386351
  9. A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata. Math. Syst. Theory 3 (1969), 186–192. Zbl0179.02501MR250789
  10. A. Cobham, Uniform-tag sequences. Math. Syst. Theory 6 (1972), 164–192. Zbl0253.02029MR457011
  11. D. Caucal, On the regular structure of prefix rewriting. Theor. Comp. Sci. 106 (1992), 61–86. Zbl0780.68077MR1193533
  12. D. Caucal, On infinite transition graphs having a decidable monadic theory. Theor. Comp. Sci. 290 (2003), 79–115. Zbl1019.68066MR1935687
  13. S. Eilenberg, Automata, languages and machines, Vol. A. Academic Press, 1974. Zbl0317.94045MR530382
  14. S. Ferenczi, Substitutions on an infinite alphabet. Ann. Inst. Fourier 56 nº7 (2006), 2315–2343. Zbl1147.37007MR2290783
  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. Zbl1084.11045MR2163909
  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. Zbl1041.11008MR1723472
  17. J. Hartmanis et H. Shank, On the recognition of primes by automata. J. Assoc. Comput. Mach. 15 (1968), 382–389. Zbl0164.05201MR235916
  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. Zbl1121.68090MR2290787
  19. M. Le Gonidec, Drunken man infinite words complexity. RAIRO-Theor. Inf. Appl. 42 (2008), 599–613. Zbl1188.68217MR2434037
  20. C. Mauduit, Propriétés arithmétiques des substitutions et automates infinis. Ann. Inst. Fourier 56 nº7 (2006), 2525–2549. Zbl1147.11016MR2290789
  21. M. Minsky et S. Papert, Unrecognizable sets of numbers. J. Assoc. Comput. Mach. 13 (1966), 281–286. Zbl0166.00601MR207481
  22. D. Muller et P. Shupp, The theory of ends, pushdown automata and second-order logic. Theor. Comp. Sci. 37 (1985), 51–75. Zbl0605.03005MR796313
  23. M. Rigo, Generalization of automatic sequences for numeration systems on a regular language. Theor. Comp. Sci. 244 (2000), 271–281. Zbl0945.68105MR1774400
  24. R. W. Ritchie, Finite automata and the set of squares. J. Assoc. Comput. Mach. 10 (1963), 528–531. Zbl0118.12601MR167374
  25. J. Sakarovitch, Élements de théorie des automates. Vuibert, 2003. Zbl1178.68002
  26. M.-P. Schützenberger, A remark on acceptable sets of numbers. J. Assoc. Comput. Mach. 15 (1968), 300–303. Zbl0165.02204MR238634

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.