Complexité et automates cellulaires linéaires
Berthé, Valérie
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 403-423 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 2000-01-01
@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},
     volume = {34},
     year = {2000},
     pages = {403-423},
     mrnumber = {1829235},
     zbl = {0988.68116},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/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) pp. 403-423. http://gdmltest.u-ga.fr/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