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},
     zbl = {0988.68116},
     mrnumber = {1829235},
     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
DA  - 2000///
SP  - 403
EP  - 423
VL  - 34
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2000__34_5_403_0/
UR  - https://zbmath.org/?q=an%3A0988.68116
UR  - https://www.ams.org/mathscinet-getitem?mr=1829235
LA  - fr
ID  - ITA_2000__34_5_403_0
ER  - 
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 898507 | Zbl 0641.10041

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

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

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

[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 1410286 | Zbl 0879.11010

[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 1387674 | Zbl 0854.68065

[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 1602847

[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 1479629 | Zbl 0943.11020

[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 1464242 | Zbl 1194.37002

[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 1466182 | Zbl 1096.68690

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

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

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

[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 1686451 | Zbl 0918.68068

[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 1650793 | Zbl 0894.68098

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

[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 1700824 | Zbl 0930.68090

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

[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 784265 | Zbl 0554.68053

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

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

[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 0653.10049

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