×

Limit sets of automatic sequences. (English) Zbl 1050.11026

The authors study the limit sets of multidimensional automatic sequences. For a finite set with a distinguished element \(s_0\), consider an \(\ell\)-dimensional sequence \(f\) in \(S^{\mathbb{N}^\ell}\). A sequence \((t_n)\in\mathbb{N}^{\mathbb{N}}\) is a scaling sequence, if \(({1\over t_n} X(f,t_n))\) is a Cauchy sequence with respect to the Hausdorff distance, where \[ X(f, t_n)= \{Q_\ell+\underline j\mid\|\underline j\|_\infty< t_n,\, f(\underline j)\neq s_0\} \] with \(0\)-dimensional cube \(Q_\ell\). The limit associated with a scaling sequence is a limit set of \(f\). They show that any automatic sequence has natural scaling sequences, and that a limit set of an automatic sequence is a union of primitive limit sets in some sense.

MSC:

11B85 Automata sequences
28A80 Fractals
37F40 Geometric limits in holomorphic dynamics
Full Text: DOI

References:

[1] Allouche, J.-P., Automates finis en théorie des nombres, Exposition Math., 5, 239-266 (1987) · Zbl 0641.10041
[2] Allouche, J.-P.; von Haeseler, F.; Lange, E.; Petersen, A.; Skordev, G., Linear cellular automata and automatic sequences, Parallel Comput., 23, 1577-1592 (1997)
[3] Allouche, J.-P.; von Haeseler, F.; Peitgen, H.-O.; Petersen, A.; Skordev, G., Automaticity of double sequences generated by one-dimensional linear cellular automata, Theoret. Comput. Sci., 188, 195-209 (1997) · Zbl 0943.11020
[4] Allouche, J.-P.; von Haeseler, F.; Peitgen, H.-O.; Skordev, G., Linear cellular automata, finite automata and Pascal’s triangle, Discrete Appl. Math., 66, 1-22 (1996) · Zbl 0854.68065
[5] Allouche, J.-P.; Shallit, J., The ubiquitous Prouhet-Thue-Morse sequence, (Ding, C.; Helleseth, T.; Niederreiter, H., Sequences and their Applications (1999), Springer: Springer London) · Zbl 1005.11005
[6] Barbé, A., On a class of fractal matrices IIIlimit structures and hierarchical iterated function systems, Internat. J. Bifur. Chaos, 5, 4, 1119-1156 (1995) · Zbl 0886.58046
[7] B. Bondarenko, Generalized Triangles and Pyramids of Pascal, Their Fractals, Graphs and Applications, Tashkend, Fan, 1990 (in Russian).; B. Bondarenko, Generalized Triangles and Pyramids of Pascal, Their Fractals, Graphs and Applications, Tashkend, Fan, 1990 (in Russian). · Zbl 0706.05002
[8] Christol, G., Ensembles presque périodiques \(k\)-reconnaissables, Theoret. Comput. Sci., 9, 141-145 (1979) · Zbl 0402.68044
[9] 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
[10] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[11] F.M. Dekking, M. Mendès France, A. van der Poorten, FOLDS!, Math. Intellzigencer 4 (1982) 130-138, 173-181, 190-195.; F.M. Dekking, M. Mendès France, A. van der Poorten, FOLDS!, Math. Intellzigencer 4 (1982) 130-138, 173-181, 190-195.
[12] Edgar, G., Measure, Topology and Fractal Geometry (1990), Springer: Springer Berlin, New York · Zbl 0727.28003
[13] S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, New York, 1985.; S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, New York, 1985. · Zbl 0317.94045
[14] Falconer, K., The Geometry of Fractal Sets (1985), Cambridge University Press: Cambridge University Press New York · Zbl 0587.28004
[15] F. von Haeseler, On algebraic properties of sequences generated by substitutions over a group, Habilitationsschrift, Universität Bremen, 1995.; F. von Haeseler, On algebraic properties of sequences generated by substitutions over a group, Habilitationsschrift, Universität Bremen, 1995.
[16] von Haeseler, F.; Peitgen, H.-O.; Skordev, G., Pascal triangle, dynamical systems and attractors, Ergodic Theory Dynamical Systems, 12, 479-486 (1992) · Zbl 0784.58032
[17] von Haeseler, F.; Peitgen, H.-O.; Skordev, G., Cellular automata, matrix substitutions and fractals, Ann. Math. Artif. Intell., 8, 345-362 (1993) · Zbl 0866.68069
[18] von Haeseler, F.; Peitgen, H.-O.; Skordev, G., On the fractal structure of rescaled evolution set of Carlitz sequences of polynomials, Discrete Appl. Math., 103, 89-109 (2000) · Zbl 0958.68110
[19] von Haeseler, F.; Peitgen, H.-O.; Skordev, G., On the fractal structure of rescaled evolution sets of cellular automata and attractors of dynamical systems I, Internat. J. Bifur. Chaos, 11, 4, 913-926 (2001) · Zbl 1090.37504
[20] von Haeseler, F.; Peitgen, H.-O.; Skordev, G., On the fractal structure of rescaled evolution sets of cellular automata and attractors of dynamical systems II, Internat. J. Bifur. Chaos, 11, 4, 927-941 (2001) · Zbl 1090.37505
[21] W. Jürgensen, Automaticity of solutions of Mahler equations, Ph.D. Thesis, Univeristät Bremen, 2000.; W. Jürgensen, Automaticity of solutions of Mahler equations, Ph.D. Thesis, Univeristät Bremen, 2000.
[22] Kuratowski, C., Topology (1966), Academic Press: Academic Press New York · Zbl 0158.40802
[23] Lange, E.; Peitgen, H.-O.; Skordev, G., Fractal patterns in Gaussian and Stirling number tables, Ars Combin., 48, 3-26 (1998) · Zbl 0963.11014
[24] Mauldin, R. D.; Williams, S., Hausdorff dimension in graph directed constructions, Trans. Amer. Math. Soc., 309, 811-829 (1989) · Zbl 0706.28007
[25] Peitgen, H.-O.; Jürgens, H.; Saupe, D., Chaos and Fractals (1992), Springer: Springer Berlin, New York · Zbl 0779.58004
[26] A. Petersen, Automatic sequences, rational functions and geometry, Ph.D. Thesis, Universität Bremen, 1997.; A. Petersen, Automatic sequences, rational functions and geometry, Ph.D. Thesis, Universität Bremen, 1997. · Zbl 0997.11505
[27] O. Salon, Suites automatiques à multi-indices, Séminaire de Théorie des nombres Bordeaux, Exp. 4, 1986-1987, pp. 4-01-4-27.; O. Salon, Suites automatiques à multi-indices, Séminaire de Théorie des nombres Bordeaux, Exp. 4, 1986-1987, pp. 4-01-4-27. · Zbl 0653.10049
[28] Sved, M.; Pitman, J., Divisibility of binomial coefficients by prime powers a geometrical approach, Ars Combin., 26 A, 197-222 (1988) · Zbl 0673.10011
[29] Takahashi, S., Self-similarity of linear cellular automata, J. Comput. Sci., 44, 114-140 (1992) · Zbl 0743.68105
[30] Willson, S., Cellular automata can generate fractals, Discrete Appl. Math., 8, 91-99 (1984) · Zbl 0533.68051
[31] Willson, S., Calculating growth rates and moments for additive cellular automata, Discrete Appl. Math., 35, 47-65 (1992) · Zbl 0738.68060
[32] Wolfram, S., Theory and Application of Cellular Automata (1996), World Scientific Publishing Company Pte. Lid: World Scientific Publishing Company Pte. Lid Singapore
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.