[en] We prove that the subsets of N^d 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.
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie ; University of Waterloo > School of Computer Science > Jeffrey Shallit
Lacroix, Anne ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Rampersad, Narad ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Multi-dimensional sets recognizable in all abstract numeration systems
P.-Y. Angrand and J. Sakarovitch, Radix enumeration of rational languages. RAIRO-Theor. Inf. Appl. 44 (2010) 19-36.
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).
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.
É. Charlier, T. Kärki and M. Rigo, Multidimensional generalized automatic sequences and shape-symmetric morphic words. Discrete Math. 310 (2010) 1238-1252.
A. Cobham, On the base-dependence of set of numbers recognizable by finite automata. Math. Syst. Theory 3 (1969) 186-192.
S. Eilenberg, Automata, languages, and machines A, Pure and Applied Mathematics 58. Academic Press, New York (1974).
S. Eilenberg, C.C. Elgot and J.C. Shepherdson, Sets recognised by n-tape automata. J. Algebra 13 (1969) 447-464.
Ch. Frougny and J. Sakarovitch, Synchronized rational relations of finite and infinite words. Theoret. Comput. Sci. 108 (1993) 45-82.
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).
S. Ginsburg and E.H. Spanier, Semigroups, Presburger formulas and languages. Pac. J. Math. 16 (1966) 285-296.
P. Lecomte and M. Rigo, Numeration systems on a regular language. Theor. Comput. Syst. 34 (2001) 27-44.
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).
J. Ramírez Alfonsín, The Diophantine Frobenius problem, Oxford Lecture Series in Mathematics and its Applications 30. Oxford (2005).
M. Rigo and A. Maes, More on generalized automatic sequences. J. Autom. Lang. Comb. 7 (2002) 351-376.
S. Rubin, Automatic Structures. Ph.D. thesis, University of Auckland, New Zealand (2004).
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.
