Multi-dimensional sets recognizable in all abstract numeration systems
Charlier, Émilie ; Lacroix, Anne ; Rampersad, Narad
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012), p. 51-65 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We prove that the subsets of that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.

Publié le : 2012-01-01
DOI : https://doi.org/10.1051/ita/2011112
Classification:  68Q45 
@article{ITA_2012__46_1_51_0,
     author = {Charlier, \'Emilie and Lacroix, Anne and Rampersad, Narad},
     title = {Multi-dimensional sets recognizable in all abstract numeration systems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {46},
     year = {2012},
     pages = {51-65},
     doi = {10.1051/ita/2011112},
     mrnumber = {2904960},
     zbl = {1254.68132},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2012__46_1_51_0}
}

Charlier, Émilie; Lacroix, Anne; Rampersad, Narad. Multi-dimensional sets recognizable in all abstract numeration systems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) pp. 51-65. doi : 10.1051/ita/2011112. http://gdmltest.u-ga.fr/item/ITA_2012__46_1_51_0/

[1] P.-Y. Angrand and J. Sakarovitch, Radix enumeration of rational languages. RAIRO-Theor. Inf. Appl. 44 (2010) 19-36. | Numdam | MR 2604933 | Zbl 1186.68243

[2] V. Berthé, C. Frougny, M. Rigo and J. Sakarovitch, On the cost and complexity of the successor function, in Proceedings of WORDS 2007. P. Arnoux, N. Bédaride and J. Cassaigne Eds., CIRM, Luminy, Marseille (2007).

[3] V. Bruyère, G. Hansel, C. Michaux and R. Villemaire, Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. 1 (1994) 191-238. | MR 1318968 | Zbl 0804.11024

[4] É. Charlier, T. Kärki and M. Rigo, Multidimensional generalized automatic sequences and shape-symmetric morphic words. Discrete Math. 310 (2010) 1238-1252. | MR 2579856 | Zbl 1231.05010

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

[6] S. Eilenberg, Automata, languages, and machines A, Pure and Applied Mathematics 58. Academic Press, New York (1974). | MR 530382 | Zbl 0317.94045

[7] S. Eilenberg, C.C. Elgot and J.C. Shepherdson, Sets recognised by n-tape automata. J. Algebra 13 (1969) 447-464. | MR 249213 | Zbl 0207.02002

[8] Ch. Frougny and J. Sakarovitch, Synchronized rational relations of finite and infinite words. Theoret. Comput. Sci. 108 (1993) 45-82. | MR 1203822 | Zbl 0783.68065

[9] Ch. Frougny and J. Sakarovitch, Number representation and finite automata, in Combinatorics, Automata, and Number Theory, Encyclopedia of Mathematics and its Applications 135. V. Berthé and M. Rigo Eds., Cambridge (2010). | MR 2766740 | Zbl 1216.68142

[10] S. Ginsburg and E.H. Spanier, Semigroups, Presburger formulas and languages. Pac. J. Math. 16 (1966) 285-296. | MR 191770 | Zbl 0143.01602

[11] P. Lecomte and M. Rigo, Numeration systems on a regular language. Theor. Comput. Syst. 34 (2001) 27-44. | MR 1799066 | Zbl 0969.68095

[12] P. Lecomte and M. Rigo, Abstract numeration systems, in Combinatorics, Automata, and Number Theory, Encyclopedia of Mathematics and its Applications 135. V. Berthé and M. Rigo Eds., Cambridge (2010). | MR 2766741 | Zbl 1216.68147

[13] J. Ramírez Alfonsín, The Diophantine Frobenius problem, Oxford Lecture Series in Mathematics and its Applications 30. Oxford (2005). | Zbl 1134.11012

[14] M. Rigo and A. Maes, More on generalized automatic sequences. J. Autom. Lang. Comb. 7 (2002) 351-376. | MR 1957696 | Zbl 1033.68069

[15] S. Rubin, Automatic Structures. Ph.D. thesis, University of Auckland, New Zealand (2004). | Zbl 1058.68070

[16] A.L. Semenov, The Presburger nature of predicates that are regular in two number systems. Sibirsk. Math. Ž. 18 (1977) 403-418, 479 (in Russian). English translation in Sib. J. Math. 18 (1977) 289-300. | MR 450050 | Zbl 0369.02023