×

Regular maps in generalized number systems. (English) Zbl 0957.11014

The paper gives a generalization of the notion of automatic [cf. A. Cobham, Math. Syst. Theory 3, 186-192 (1969; Zbl 0179.02501); ibid. 6, 164-192 (1972; Zbl 0253.02029)] and regular maps [cf. J. P. Allouche and J. Shallit, Theor. Comput. Sci. 98, 163-197 (1992; Zbl 0774.68072)] to canonical number systems in algebraic number fields and to linear numeration systems with a linear recurring base sequence. The paper gives a detailed study of the properties of such maps and extends the theory originally developed for the case of the \(q\)-adic digital expansion of the positive integers to this more general setting.

MSC:

11B85 Automata sequences
11R11 Quadratic extensions
11A63 Radix representation; digital problems
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] ALLOUCHE J.-P.: q-regular sequences and other generalizations of q-automatic sequences. Lecture Notes in Comput. Sci. 583, Springer, New York, 1992, pp. 15-23.
[2] ALLOUCHE J.-P.: Finite automata and arithmetic. Seminaire Lotharingien de Combinatoire B30c, 1993, pp. 1-23. · Zbl 0903.11009
[3] ALLOUCHE J.-P.-CATELAND E.-GILBERT W. J.-PEITGEN H.-O.- SHALLIT J.-SKORDEV G.: Automatic maps in exotic numeration systems. Theory Comput. Syst. (Formerly: Math. Systems Theory) 30 (1997), 285-331. · Zbl 0870.68105 · doi:10.1007/BF02679463
[4] ALLOUCHE J.-P.-MORTON P.-SHALLIT J.: Pattern spectra, substring enumeration, and automatic sequences. Theoret. Comput. Sci. 94 (1.992), 161-174. · Zbl 0753.11012 · doi:10.1016/0304-3975(92)90032-B
[5] ALLOUCHE J.-P.-SHALLIT J.: The ring of k-regular sequences. Theoret. Comput. Sci. 98 (1992), 163-187. · Zbl 0774.68072 · doi:10.1016/0304-3975(92)90001-V
[6] CHRISTOL G.: Ensembles presque-periodiques k-reconnaissables. Theoret. Comput. Sci. 9 (1979), 141-145. · Zbl 0402.68044 · doi:10.1016/0304-3975(79)90011-2
[7] CHRISTOL G.-KAMAE T.-MENDES FRANCE M.-RAUZY G.: Suites algebriques, automates et substitutions. Bull. Soc. Math. France 108 (1980), 401-419. · Zbl 0472.10035
[8] COBHAM A.: On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3 (1969), 186-192. · Zbl 0179.02501 · doi:10.1007/BF01746527
[9] COBHAM A.: Uniform tag sequences. Math. Systems Theory 6 (1972), 164-192. · Zbl 0253.02029 · doi:10.1007/BF01706087
[10] DEKKING F. M.-MENDES FRANCE M.-VAN DER POORTEN A. J.: Folds!. Math. Intelligencer 4 (1982), 130-138, 173-181, 190-195. · Zbl 0493.10001 · doi:10.1007/BF03024244
[11] FRAENKEL A. S.: Systems of numeration. Amer. Math. Monthly 92 (1985), 105-114. · Zbl 0568.10005 · doi:10.2307/2322638
[12] FROUGNY C.: Confluent linear numeration systems. Theoret. Comput. Sci. 106 (1992), 183-219. · Zbl 0787.68057 · doi:10.1016/0304-3975(92)90249-F
[13] FROUGNY C.-SOLOMYAK B.: On representation of integers in linear numeration systems. Ergodic Theory of Zd actions. Proceedings of the Warwick Symposium, Warwick, UK, 1993-94 (M. Pollicott et al., London Math. Soc. Lecture Note Ser. 228, Cambridge University Press, Cambridge, 1996, pp. 345-368.
[14] GRABNER P. G.-KIRSCHENHOFER P.-PRODINGER H.: The sum of digits function for complex bases. J. London Math. Soc. 57 (1998), 20-40. · Zbl 0959.11045 · doi:10.1112/S0024610798005663
[15] KÁTAI I.-KOVÁCS B.: Kanonische Zahlensysteme in der Theorie der quadratischen algebraischen Zahlen. Acta Sci. Math. (Szeged) 42 (1980), 99-107. · Zbl 0386.10007
[16] KÁTAI I.-KOVÁCS B.: Canonical number systems in imaginary quadratic fields. Acta Math. Acad. Sci. Hungar. 37 (1981), 159-164. · Zbl 0477.10012 · doi:10.1007/BF01904880
[17] KÁTAI I.-SZABO J.: Canonical number systems for complex integers. Acta Sci. Math. (Szeged) 37 (1975), 255-260.
[18] KIMBERLING C.: Numeration systems and fractal sequences. Acta Arith. 73 (1995), 103-117. · Zbl 0834.11010
[19] KNUTH D. E.: The Art of Computer Programming. Vol. 2. Seminumerical Algorithms (2nd, Addison Wesley, Reading, 1981. · Zbl 0477.65002
[20] KOVÁCS B.: CNS rings. Topics in Classical Number Theory, Vol. II (G. Halasz, Colloq. Math. Soc. Janos Bolyai 34, North-Holland, Amsterdam, 1984, pp. 961-971. · Zbl 0558.10006
[21] KOVÁCS B.-PETHO A.: Number systems in integral domains, especially in orders of algebraic number fields. Acta Sci. Math. (Szeged) 55 (1991), 287-299. · Zbl 0760.11002
[22] MORTON P.-MOURANT W.: Paper folding, digit patterns and groups of arithmetic fractals. Proc. London Math. Soc. 59 (1989), 253-293. · Zbl 0694.10009 · doi:10.1112/plms/s3-59.2.253
[23] SALON O.: Suites automatiques á multi-indices et algebricité. C. R. Acad. Sci. Paris Ser. I Math. 305 (1987), 501-504. · Zbl 0628.10007
[24] SALON O.: Proprietes arithmetiques des automates multidimensionnels. Thése, University Bordeaux I, Bordeaux, 1989.
[25] SCHEICHER K.: Kanonische Ziffernsysteme und Automaten. Grazer Math. Ber. 333, Karl-Franzens-Univ. Graz, Graz, 1997, pp. 1-17. · Zbl 0905.11009
[26] SCHEICHER K.: Zifferndarstellungen, lineare Rekursionen und Automaten. PhD Thesis, TU Graz, Graz, 1997.
[27] SHALLIT J.: A generalization of automatic sequences. Theoret. Comput. Sci. 61 (1988), 1-16. · Zbl 0662.68052 · doi:10.1016/0304-3975(88)90103-X
[28] THUSWALDNER J.: Elementary properties of canonical number systems in quadratic fields. Applications of Fibonacci Numbers, Vol. 7 (Graz 1996), Kluwer Acad. Publ., Dordrecht, 1998, pp. 405-414. · Zbl 0917.11054
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.