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
Access Full Article
top
Abstract
topHow to cite
topCharlier, É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- 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. Theory3 (1969) 186–192.
- S. Eilenberg, Automata, languages, and machinesA, Pure and Applied Mathematics58. Academic Press, New York (1974).
- S. Eilenberg, C.C. Elgot and J.C. Shepherdson, Sets recognised by n-tape automata. J. Algebra13 (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 Applications135. 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 Applications135. V. Berthé and M. Rigo Eds., Cambridge (2010).
- J. Ramírez Alfonsín, The Diophantine Frobenius problem, Oxford Lecture Series in Mathematics and its Applications30. 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.
NotesEmbed ?
topYou 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.