Multi-dimensional sets recognizable in all abstract numeration systems

Émilie Charlier; Anne Lacroix; Narad Rampersad

RAIRO - Theoretical Informatics and 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 46.1 (2012): 51-65. <http://eudml.org/doc/222047>.

@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},
keywords = {Finite automata; numeration systems; recognizable sets of integers; multi-dimensional setting; numeration system; regular language; finite automata.},
language = {eng},
month = {3},
number = {1},
pages = {51-65},
publisher = {EDP Sciences},
title = {Multi-dimensional sets recognizable in all abstract numeration systems},
url = {http://eudml.org/doc/222047},
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
DA - 2012/3//
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/222047
ER -

References

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

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.