×

Bertrand numeration systems and recognizability. (English) Zbl 0957.11015

Summary: There exist various well-known characterizations of sets of numbers recognizable by a finite automaton, when they are represented in some integer base \(p\geqslant 2\). We show how to modify these characterizations, when integer bases \(p\) are replaced by linear numeration systems whose characteristic polynomial is the minimal polynomial of a Pisot number. We also prove some related interesting properties.

MSC:

11B85 Automata sequences
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Allouche, J.-P., q-regular sequences and other generalizations of q-automatic sequences, (), 15-23
[2] Allouche, J.-P.; Cateland, E.; Gilbert, W.J.; Peitgen, H.-O.; Shallit, J.O.; Skordev, G., Automatic maps in exotic numeration systems, Math. systems theory, (1996), to appear. · Zbl 0870.68105
[3] Béal, M.P., Codage symbolique, (1993), Masson
[4] Bertrand-Mathis, A., Comment écrire LES nombres entiers dans une base qui n’est pas entière, Acta math. acad. sci. Hungary, 54, 237-241, (1989) · Zbl 0695.10005
[5] Bertrand-Mathis, A., Développement en base θ, répartition modulo un de la suite (n)b⩾0, langages codés et θ-shift, Bull. soc. math. France, 114, 271-323, (1986) · Zbl 0628.58024
[6] Bès, A., An extension of the cobham-semenov theorem, (1996), preprint · Zbl 0958.03025
[7] Bruyère, V.; Hansel, G., Recognizable sets of numbers in nonstandard bases, Lecture notes in computer science, Vol. 911, 167-179, (1995)
[8] Bruyère, V.; Hansel, G.; Michaux, C.; Villemaire, R., Logic and p-recognizable sets of integers, Bull. belg. math. soc., 1, 191-238, (1994) · Zbl 0804.11024
[9] Büchi, J.R., Weak second-order arithmetic and finite automata, Z. math. logik grundlag. math., 6, 66-92, (1960) · Zbl 0103.24705
[10] Christol, G.; Kamae, T.; Mendès France, M.; Rauzy, G., Suites algébriques, automates et substitutions, Bull. soc. math. France, 108, 401-419, (1980) · Zbl 0472.10035
[11] Cobham, A., On the base-dependence of sets of numbers recognizable by finite automata, Math. systems theory, 3, 186-192, (1969) · Zbl 0179.02501
[12] Cobham, A., Uniform tag systems, Math. systems theory, 6, 164-192, (1972) · Zbl 0253.02029
[13] Eilenberg, S., ()
[14] Fabre, S., Substitutions et independence des systèmes de numération, ()
[15] Fraenkel, A.S., Systems of numeration, Amer. math. monthly, 92, 105-114, (1985) · Zbl 0568.10005
[16] Frougny, C., Representations of numbers and finite automata, Math. systems theory, 25, 37-60, (1992) · Zbl 0776.11005
[17] Frougny, C.; Solomyak, B., On representations of integers in linear numeration systems, (), 345-368 · Zbl 0856.11007
[18] Hansel, G., Sur la syndéticité d’une partie (θ, θ′)-reconnaissable de \(N\), (1995), manuscript
[19] Hodgson, B.R., Décidabilité par automate fini, Ann. sci. math. Québec, 7, 39-57, (1983) · Zbl 0531.03007
[20] Hollander, M., Greedy numeration systems and regularity, (1995), preprint
[21] Loraud, N., Β-shift, systèmes de numération et automates, (1995), preprint · Zbl 0843.11013
[22] Parry, W., On the β-expansions of real numbers, Acta math. acad. sci. hungar., 11, 401-416, (1960) · Zbl 0099.28103
[23] Perrin, D., Finite automata, (), 2-57 · Zbl 0900.68312
[24] Point, F.; Bruyère, V., On the cobham-semenov theorem, Theory comput. systems, 30, 197-220, (1997) · Zbl 0870.68065
[25] Shallit, J., Numeration systems, linear recurrences and regular sets, Lecture notes in computer science, Vol. 623, 89-100, (1992)
[26] Villemaire, R., The theory of \(〈N, +, Vk, Vl〉\) is undecidable, Theoret. comput. sci., 106, 337-349, (1992) · Zbl 0773.03008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.