Multi-dimensional sets recognizable in all abstract numeration systems
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 51-65.

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.

DOI : 10.1051/ita/2011112
Classification : 68Q45
Mots-clés : finite automata, numeration systems, recognizable sets of integers, multi-dimensional setting 
@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},
     pages = {51--65},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {1},
     year = {2012},
     doi = {10.1051/ita/2011112},
     mrnumber = {2904960},
     zbl = {1254.68132},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2011112/}
}
TY  - JOUR
AU  - Charlier, Émilie
AU  - Lacroix, Anne
AU  - Rampersad, Narad
TI  - Multi-dimensional sets recognizable in all abstract numeration systems
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2012
SP  - 51
EP  - 65
VL  - 46
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011112/
DO  - 10.1051/ita/2011112
LA  - en
ID  - ITA_2012__46_1_51_0
ER  - 
%0 Journal Article
%A Charlier, Émilie
%A Lacroix, Anne
%A Rampersad, Narad
%T Multi-dimensional sets recognizable in all abstract numeration systems
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2012
%P 51-65
%V 46
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2011112/
%R 10.1051/ita/2011112
%G en
%F 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) no. 1, pp. 51-65. doi : 10.1051/ita/2011112. http://www.numdam.org/articles/10.1051/ita/2011112/

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

[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 | Zbl

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

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

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

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

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

[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 | Zbl

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

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

[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 | Zbl

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

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

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

[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 | Zbl

Cité par Sources :