Multi-dimensional sets recognizable in all abstract numeration systems

Émilie Charlier; Anne Lacroix; Narad Rampersad

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2012)

  • Volume: 46, Issue: 1, page 51-65
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Charlier, Émilie, Lacroix, Anne, and Rampersad, Narad. "Multi-dimensional sets recognizable in all abstract numeration systems." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 46.1 (2012): 51-65. <http://eudml.org/doc/273043>.

@article{Charlier2012,
abstract = {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.},
author = {Charlier, Émilie, Lacroix, Anne, Rampersad, Narad},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {finite automata; numeration systems; recognizable sets of integers; multi-dimensional setting; numeration system; regular language; finite automata.},
language = {eng},
number = {1},
pages = {51-65},
publisher = {EDP-Sciences},
title = {Multi-dimensional sets recognizable in all abstract numeration systems},
url = {http://eudml.org/doc/273043},
volume = {46},
year = {2012},
}

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
PB - EDP-Sciences
VL - 46
IS - 1
SP - 51
EP - 65
AB - 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.
LA - eng
KW - finite automata; numeration systems; recognizable sets of integers; multi-dimensional setting; numeration system; regular language; finite automata.
UR - http://eudml.org/doc/273043
ER -

References

top
  1. [1] P.-Y. Angrand and J. Sakarovitch, Radix enumeration of rational languages. RAIRO–Theor. Inf. Appl. 44 (2010) 19–36. Zbl1186.68243MR2604933
  2. [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. [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. Zbl0804.11024MR1318968
  4. [4] É. Charlier, T. Kärki and M. Rigo, Multidimensional generalized automatic sequences and shape-symmetric morphic words. Discrete Math.310 (2010) 1238–1252. Zbl1231.05010MR2579856
  5. [5] A. Cobham, On the base-dependence of set of numbers recognizable by finite automata. Math. Syst. Theory3 (1969) 186–192. Zbl0179.02501MR250789
  6. [6] S. Eilenberg, Automata, languages, and machines A, Pure and Applied Mathematics 58. Academic Press, New York (1974). Zbl0317.94045MR530382
  7. [7] S. Eilenberg, C.C. Elgot and J.C. Shepherdson, Sets recognised by n-tape automata. J. Algebra13 (1969) 447–464. Zbl0207.02002MR249213
  8. [8] Ch. Frougny and J. Sakarovitch, Synchronized rational relations of finite and infinite words. Theoret. Comput. Sci.108 (1993) 45–82. Zbl0783.68065MR1203822
  9. [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). Zbl1216.68142MR2766740
  10. [10] S. Ginsburg and E.H. Spanier, Semigroups, Presburger formulas and languages. Pac. J. Math. 16 (1966) 285–296. Zbl0143.01602MR191770
  11. [11] P. Lecomte and M. Rigo, Numeration systems on a regular language. Theor. Comput. Syst.34 (2001) 27–44. Zbl0969.68095MR1799066
  12. [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). Zbl1216.68147MR2766741
  13. [13] J. Ramírez Alfonsín, The Diophantine Frobenius problem, Oxford Lecture Series in Mathematics and its Applications 30. Oxford (2005). Zbl1134.11012
  14. [14] M. Rigo and A. Maes, More on generalized automatic sequences. J. Autom. Lang. Comb.7 (2002) 351–376. Zbl1033.68069MR1957696
  15. [15] S. Rubin, Automatic Structures. Ph.D. thesis, University of Auckland, New Zealand (2004). Zbl1058.68070
  16. [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. Zbl0369.02023MR450050

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.