×

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
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allouche, J.-P., \(q\)-regular sequences and other generalizations of \(q\)-automatic sequences, (Proc. Latin ’92. Proc. Latin ’92, Lecture Notes in Computer Science, Vol. 583 (1992)), 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 \(( xθ^n)_{b\)⩾0 · 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) · Zbl 1510.11026
[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., (Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[14] Fabre, S., Substitutions et independence des systèmes de numération, (Thèse (1992), Université Aix-Marseille II)
[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, (Pollicot, M.; Schmidt, K., Ergodic Theory of \(Z^d\)-Actions. Ergodic Theory of \(Z^d\)-Actions, London Math. Soc. Lecture Note, Vol. 228 (1996)), 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, (Van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. B (1990), Eisevier: Eisevier Amsterdam), 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) · Zbl 1425.11015
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.