Complexité et automates cellulaires linéaires

 Access to full text

 Full (PDF)

1. [1] J.-P. Allouche, Automates finis en théorie des nombres. Exposition. Math. 5 (1987) 239-266. Zbl0641.10041MR898507
2. [2] J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc. 1 (1994) 133-143. Zbl0803.68094MR1318964
3. [3] J.-P. Allouche et V. Berthé, Triangle de Pascal, complexité et automates. Bull. Belg. Math. Soc. 4 (1997) 1-23. Zbl0922.11012MR1440666
4. [4] J.-P. Allouche et J. Shallit, The ring of k-regular sequences. Theoret. Cornput. Sci. 98 (1992) 163-197. Zbl0774.68072MR1166363
5. [5] J.-P. Allouche et D. Berend, Complexity of the sequence of middle-binomial coefficients (en préparation). 
6. [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. Zbl0879.11010MR1410286
7. [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. Zbl0854.68065MR1387674
8. [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. Zbl0943.11020MR1602847
9. [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. Zbl0943.11020MR1479629
10. [10] F. Blanchard, P. Kurka et A. Maass, Topological and measure-theoretic properties of one-dimensional cellular automata. Phys. D 103 (1997) 86-99. Zbl1194.37002MR1464242
11. [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. Zbl1096.68690MR1466182
12. [12] A. Cobham, Uniform tag sequences. Math. Systems Theory 6 (1972) 164-192. Zbl0253.02029MR457011
13. [13] C. Grillenberger, Construction of striclty ergodic Systems I. Given entropy. Z. Wahrsch. Verw. Gebiete 25 (1973) 323-334. Zbl0253.28004MR340544
14. [14] B. Litow et P. Dumas, Additive cellular automata and algebraic series. Theoret. Comput. Sci. 119 (1993) 345-354. Zbl0787.68074MR1244299
15. [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. Zbl0918.68068MR1686451
16. [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. Zbl0894.68098MR1650793
17. [17] G. Manzini et L. Margara, Invertible cellular automata over Zm: Algorithmic and dynamical aspects. J. Comput. System Sci. 56 (1998) 60-67. Zbl0914.68144MR1610931
18. [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. Zbl0930.68090MR1700824
19. [19] O. Martin, A. Odlyzko et S. Wolfram, Algebraic properties of cellular automata. Comm. Math. Phys. 93 (1984) 219-258. Zbl0564.68038MR742194
20. [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. Zbl0554.68053MR784265
21. [21] A. D. Robinson, Fast computation of additive cellular automata. Complex Systems 1 (1987) 211-216. Zbl0655.68064MR891522
22. [22] O. Salon, Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris Sér. I Math. 305 (1987) 501-504. Zbl0628.10007MR916320
23. [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. Zbl0653.10049
24. [24] J. W. Sander, R. Tijdeman, The complexity of fonctions on lattices. Theoret. Comput. Sci. (à paraître). Zbl1005.68118