Hostname: page-component-74656f9884-54qdv Total loading time: 0 Render date: 2026-11-10T07:07:23.231Z Has data issue: false hasContentIssue false
  • English
  • Français

Multi-dimensional sets recognizablein all abstract numeration systems

Published online by Cambridge University Press:  25 August 2011

Émilie Charlier ,
Anne Lacroix  and
Narad Rampersad
Émilie Charlier
Affiliation:
Department of Mathematics, University of Liège, Grande Traverse 12 (B37), 4000 Liège, Belgium. echarlier@ulg.ac.be, A.Lacroix@ulg.ac.be, nrampersad@ulg.ac.be
Anne Lacroix
Affiliation:
Department of Mathematics, University of Liège, Grande Traverse 12 (B37), 4000 Liège, Belgium. echarlier@ulg.ac.be, A.Lacroix@ulg.ac.be, nrampersad@ulg.ac.be
Narad Rampersad
Affiliation:
Department of Mathematics, University of Liège, Grande Traverse 12 (B37), 4000 Liège, Belgium. echarlier@ulg.ac.be, A.Lacroix@ulg.ac.be, nrampersad@ulg.ac.be

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We prove that the subsets ofthat 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.

Keywords

Finite automatanumeration systemsrecognizable sets of integersmulti-dimensional setting

References

Références

Angrand, P.-Y. and Sakarovitch, J., Radix enumeration of rational languages. RAIRO–Theor. Inf. Appl. 44 (2010) 19–36. Google Scholar
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).
Bruyère, V., Hansel, G., Michaux, C. and Villemaire, R., Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. 1 (1994) 191–238. Google Scholar
Charlier, É., Kärki, T. and Rigo, M., Multidimensional generalized automatic sequences and shape-symmetric morphic words. Discrete Math. 310 (2010) 1238–1252. Google Scholar
Cobham, A., On the base-dependence of set of numbers recognizable by finite automata. Math. Syst. Theory 3 (1969) 186–192. Google Scholar
S. Eilenberg, Automata, languages, and machines A, Pure and Applied Mathematics 58. Academic Press, New York (1974).
Eilenberg, S., Elgot, C.C. and Shepherdson, J.C., Sets recognised by n-tape automata. J. Algebra 13 (1969) 447–464. Google Scholar
Frougny, Ch. and Sakarovitch, J., Synchronized rational relations of finite and infinite words. Theoret. Comput. Sci. 108 (1993) 45–82. Google Scholar
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).
Ginsburg, S. and Spanier, E.H., Semigroups, Presburger formulas and languages. Pac. J. Math. 16 (1966) 285–296. Google Scholar
Lecomte, P. and Rigo, M., Numeration systems on a regular language. Theor. Comput. Syst. 34 (2001) 27–44. Google Scholar
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).
Rigo, M. and Maes, A., More on generalized automatic sequences. J. Autom. Lang. Comb. 7 (2002) 351–376. Google Scholar
S. Rubin, Automatic Structures. Ph.D. thesis, University of Auckland, New Zealand (2004).
Semenov, A.L., 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. Google Scholar