Complexité et automates cellulaires linéaires
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) no. 5, pp. 403-423. 
@article{ITA_2000__34_5_403_0,
     author = {Berth\'e, Val\'erie},
     title = {Complexit\'e et automates cellulaires lin\'eaires},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {403--423},
     publisher = {EDP-Sciences},
     volume = {34},
     number = {5},
     year = {2000},
     mrnumber = {1829235},
     zbl = {0988.68116},
     language = {fr},
     url = {http://www.numdam.org/item/ITA_2000__34_5_403_0/}
}
TY  - JOUR
AU  - Berthé, Valérie
TI  - Complexité et automates cellulaires linéaires
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2000
SP  - 403
EP  - 423
VL  - 34
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2000__34_5_403_0/
LA  - fr
ID  - ITA_2000__34_5_403_0
ER  - 
%0 Journal Article
%A Berthé, Valérie
%T Complexité et automates cellulaires linéaires
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2000
%P 403-423
%V 34
%N 5
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_2000__34_5_403_0/
%G fr
%F ITA_2000__34_5_403_0
Berthé, Valérie. Complexité et automates cellulaires linéaires. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) no. 5, pp. 403-423. http://www.numdam.org/item/ITA_2000__34_5_403_0/

[1] J.-P. Allouche, Automates finis en théorie des nombres. Exposition. Math. 5 (1987) 239-266. | MR | Zbl

[2] J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc. 1 (1994) 133-143. | MR | Zbl

[3] J.-P. Allouche et V. Berthé, Triangle de Pascal, complexité et automates. Bull. Belg. Math. Soc. 4 (1997) 1-23. | MR | Zbl

[4] J.-P. Allouche et J. Shallit, The ring of k-regular sequences. Theoret. Cornput. Sci. 98 (1992) 163-197. | MR | Zbl

[5] J.-P. Allouche et D. Berend, Complexity of the sequence of middle-binomial coefficients (en préparation).

[6] J.-P. Allouche, E. Cateland, H.-O. Peitgen, J. Shallit et G. Skordev, Automatic maps on a semiring with digits. Fractals 3 (1995) 663-677. | MR | Zbl

[7] J.-P. Allouche, F. Von Haeseler, H.-O. Peitgen et G. Skordev, Linear cellular automata, finite automata and Pascal's triangle. Discrete Appl. Math. 66 (1966) 1-22. | MR | Zbl

[8] J.-P. Allouche, F. Von Haeseler, H.-O. Peitgen, A. Petersen et G. Skordev, Linear cellular automata and automatic sequences. Parallel Comput. 23 (1997) 1577-1592. | MR

[9] J.-P. Allouche, F. Von Haeseler, H.-O. Peitgen, A. Petersen et G. Skordev, Automaticity of double sequences generated by one-dimensional linear cellular automata. Theoret. Comput. Sci. 88 (1997) 195-209. | MR | Zbl

[10] F. Blanchard, P. Kurka et A. Maass, Topological and measure-theoretic properties of one-dimensional cellular automata. Phys. D 103 (1997) 86-99. | MR | Zbl

[11] 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. | MR | Zbl

[12] A. Cobham, Uniform tag sequences. Math. Systems Theory 6 (1972) 164-192. | MR | Zbl

[13] C. Grillenberger, Construction of striclty ergodic Systems I. Given entropy. Z. Wahrsch. Verw. Gebiete 25 (1973) 323-334. | MR | Zbl

[14] B. Litow et P. Dumas, Additive cellular automata and algebraic series. Theoret. Comput. Sci. 119 (1993) 345-354. | MR | Zbl

[15] G. Manzini, 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. | MR | Zbl

[16] G. Manzini et L. Margara, Attractors of D-dimensional linear cellular automata, in STACS 98. Springer, Lecture Notes in Comput. Sci. 1373 (1998) 128-138. | MR | Zbl

[17] G. Manzini et L. Margara, Invertible cellular automata over Zm: Algorithmic and dynamical aspects. J. Comput. System Sci. 56 (1998) 60-67. | MR | Zbl

[18] G. Manzini et L. Margara, A complete and efficiently computable topological classification of D-dimensional linear cellular automata over Zm. Theoret. Comput. Sci. 221 (1999) 157-177. | MR | Zbl

[19] O. Martin, A. Odlyzko et S. Wolfram, Algebraic properties of cellular automata. Comm. Math. Phys. 93 (1984) 219-258. | MR | Zbl

[20] J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés. Springer, Lecture Notes in Comput. Sci. 172 (1984) 380-389. | MR | Zbl

[21] A. D. Robinson, Fast computation of additive cellular automata. Complex Systems 1 (1987) 211-216. | MR | Zbl

[22] O. Salon, Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris Sér. I Math. 305 (1987) 501-504. | MR | Zbl

[23] 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. | Zbl

[24] J. W. Sander, R. Tijdeman, The complexity of fonctions on lattices. Theoret. Comput. Sci. (à paraître). | Zbl