Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-23T05:21:24.017Z Has data issue: false hasContentIssue false
  • English
  • Français

Complexité et automates cellulaires linéaires

Published online by Cambridge University Press:  15 April 2002

Valérie Berthé
Valérie Berthé*
Affiliation:
IML, UPR 9016, Case 907, 163 avenue de Luminy, 13288 Marseille Cedex 09, France; ([email protected])
Get access

Abstract

The aim of this paper is to evaluate the growth orderof the complexity function (in rectangles)for two-dimensional sequencesgenerated by a linear cellular automatonwith coefficients in $\mathbb{Z}/l \mathbb{Z}$ , and polynomial initial condition.We prove that the complexity functionis quadratic when l is a prime and that it increases with respect to the number of distinct prime factors of l.

Keywords

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 34 , Issue 5 , September 2000 , pp. 403 - 423
Copyright
© EDP Sciences, 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J.-P. Allouche, Automates finis en théorie des nombres. Exposition. Math. 5 (1987) 239-266.
Allouche, J.-P., Sur la complexité des suites infinies. Bull. Belg. Math. Soc. 1 (1994) 133-143.
Allouche, J.-P. et Berthé, V., Triangle de Pascal, complexité et automates. Bull. Belg. Math. Soc. 4 (1997) 1-23.
Allouche, J.-P. et Shallit, J., The ring of k-regular sequences. Theoret. Comput. Sci. 98 (1992) 163-197. CrossRef
J.-P. Allouche et D. Berend, Complexity of the sequence of middle-binomial coefficients (en préparation).
Allouche, J.-P., Cateland, E., Peitgen, H.-O., Shallit, J. et Skordev, G., Automatic maps on a semiring with digits. Fractals 3 (1995) 663-677. CrossRef
Allouche, J.-P., von Haeseler, F., Peitgen, H.-O. et Skordev, G., Linear cellular automata, finite automata and Pascal's triangle. Discrete Appl. Math. 66 (1996) 1-22. CrossRef
Allouche, J.-P., von Haeseler, F., Peitgen, H.-O., Petersen, A. et Skordev, G., Linear cellular automata and automatic sequences. Parallel Comput. 23 (1997) 1577-1592. CrossRef
Allouche, J.-P., von Haeseler, F., Peitgen, H.-O., Petersen, A. et Skordev, G., Automaticity of double sequences generated by one-dimensional linear cellular automata. Theoret. Comput. Sci. 88 (1997) 195-209. CrossRef
Blanchard, F., Kurka, P. et Maass, A., Topological and measure-theoretic properties of one-dimensional cellular automata. Phys. D 103 (1997) 86-99. CrossRef
J. Cassaigne, Special factors of sequences with linear subword complexity, in Developments in Language Theory II (DLT'95), Magdeburg (Allemagne). World Scientific (1996) 25-34.
Cobham, A., Uniform tag sequences. Math. Systems Theory 6 (1972) 164-192. CrossRef
Grillenberger, C., Construction of striclty ergodic systems I. Given entropy. Z. Wahrsch. Verw. Gebiete 25 (1973) 323-334. CrossRef
Litow, B. et Dumas, P., Additive cellular automata and algebraic series. Theoret. Comput. Sci. 119 (1993) 345-354. CrossRef
Manzini, G., Characterization of sensitive linear cellular automata with respect to the counting distance, in MFCS'98. Springer, Lecture Notes in Comput. Sci. 1450 (1998) 825-833. CrossRef
Manzini, G. et Margara, L., Attractors of D-dimensional linear cellular automata, in STACS 98. Springer, Lecture Notes in Comput. Sci. 1373 (1998) 128-138. CrossRef
Manzini, G. et Margara, L., Invertible cellular automata over $\mathbb{Z}_m$ : Algorithmic and dynamical aspects. J. Comput. System Sci. 56 (1998) 60-67. CrossRef
Manzini, G. et Margara, L., A complete and efficiently computable topological classification of D-dimensional linear cellular automata over $\mathbb{Z}_m$ . Theoret. Comput. Sci. 221 (1999) 157-177. CrossRef
Martin, O., Odlyzko, A. et Wolfram, S., Algebraic properties of cellular automata. Comm. Math. Phys. 93 (1984) 219-258. CrossRef
Pansiot, J.-J., Complexité des facteurs des mots infinis engendrés par morphismes itérés. Springer, Lecture Notes in Comput. Sci. 172 (1984) 380-389. CrossRef
Robinson, A.D., Fast computation of additive cellular automata. Complex Systems 1 (1987) 211-216.
Salon, O., Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris Sér. I Math. 305 (1987) 501-504.
O. Salon, Suites automatiques à multi-indices, Séminaire de Théorie des Nombres de Bordeaux, Exposé 4 (1986-1987) 4-01-4-27 ; suivi par un Appendice de J. Shallit, 4-29A-4-36A.
J.W. Sander, R. Tijdeman, The complexity of functions on lattices. Theoret. Comput. Sci. (à paraître).