numeration system; recognizable sets of integers; multiplication by a constant
Résumé :
[en] Generalizations of positional number systems in which N is recognizable by finite automata are obtained by describing an arbitrary infinite regular language according to the lexicographic ordering. For these systems of numeration, we show that ultimately periodic sets are recognizable. We also study translation and multiplication by constants as well as the order-dependence of the recognizability.
Disciplines :
Sciences informatiques Mathématiques
Auteur, co-auteur :
Lecomte, Pierre ; Université de Liège - ULiège > Département de mathématique > Géométrie et théorie des algorithmes
Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Langue du document :
Anglais
Titre :
Numerations systems on a regular language
Date de publication/diffusion :
2001
Titre du périodique :
Theory of Computing Systems
ISSN :
1432-4350
eISSN :
1433-0490
Maison d'édition :
Springer Science & Business Media B.V., New York, Etats-Unis - New York
M. Andraşiu, J. Dassow, G. Pǎun, A. Salomaa, Language-theoretic problems arising from Richelieu cryptosystems, Theoret. Comput. Sci. 116 (1993), 339-357.
J. Berstel, C. Reutenauer, Les séries rationnelles et leurs langages, Études et Recherches en Informatique, Masson, Paris, 1984.
A. Bertrand-Mathis, Comment écrire les nombres entiers dans une base qui n'est pas entière, Acta Math. Acad. Sci. Hungar. 54 (1989), 237-241.
V. Bruyère, G. Hansel, Bertrand numeration systems and recognizability, Theoret. Comput. Sci. 181 (1997), 17-43.
V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. 1 (1994), 191-238.
A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory 3 (1969), 186-192.
A. Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 186-192.
H. Davenport, The Higher Arithmetic, sixth edn., Cambridge University Press, Cambridge, 1992.
F. Durand, A generalization of Cobham's theorem, Theory Comput. Systems 31 (1998), 169-185.
F. Durand, Sur les ensembles d'entiers reconnaissables, J. Théor. Nombres Bordeaux 10 (1998), 65-84.
S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, New York, 1974.
A. S. Fraenkel, Systems of numeration, Amer. Math. Monthly 92 (1985), 105-114.
C. Frougny, Representations of numbers and finite automata, Math. Systems Theory 25 (1992), 37-60.
C. Frougny, B. Solomyak, On representation of integers in linear numeration systems, in Ergodic Theory of Zd Actions (Warwick, 1993-1994), pp. 345-368, London Mathematical Society Lecture Note Series, Vol. 228, Cambridge University Press, Cambridge, 1996.
C. Frougny, B. Solomyak, On representation of integers in linear numeration systems, in Ergodic Theory of Zd Actions (Warwick, 1993-1994), pp. 345-368, London Mathematical Society Lecture Note Series, Vol. 228, Cambridge University Press, Cambridge, 1996.
G. Hansel, Systèmes de numération indépendants et syndéticité, Theoret. Comput. Sci. 204 (1998), 119-130.
M. Hollander, Greedy numeration systems and regularity, Theory Comput. Systems 31 (1998), 111-133.
H. R. Lewis, C. H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, Englewood Cliffs, NJ, 1981.
N. Loraud, β-shift, systèmes de numération et automates, J. Théor. Nombres Bordeaux 7 (1995), 473-498.
A. Maes, Morphic predicates and applications to the decidability of arithmetic theories, Thesis, Université de Mons-Hainaut (1999).
G. Pǎun, A. Salomaa, Thin and slender languages, Discrete Appl. Math. 61 (1995), 257-270.
D. Perrin, Finite automata, in Handbook of Theoretical Computer Science, Vol. B, pp. 2-57. J. Van Leeuwen, ed., Elsevier, Amsterdam, 1990.
F. Point and V. Bruyère, On the Cobham-Semenov theorem, Theory Comput. Systems 30 (1997), 197-220.
H. E. Rose, A Course in Number Theory, second edn., Oxford Science, Oxford, 1996.
J. Shallit, Numeration systems, linear recurrences, and regular sets, Inform. and Comput. 113 (1994), 331-347.
S. Yablonski, Introduction aux mathématiques discrètes, Ed. Mir, Moscou, 1983.
