Complexité et automates cellulaires linéaires

Valérie Berthé

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 34, Issue: 5, page 403-423
  • ISSN: 0988-3754

Abstract

top
The aim of this paper is to evaluate the growth order of the complexity function (in rectangles) for two-dimensional sequences generated by a linear cellular automaton with coefficients in ℤ / l ℤ , and polynomial initial condition. We prove that the complexity function is quadratic when l is a prime and that it increases with respect to the number of distinct prime factors of l.

How to cite

top

Berthé, Valérie. "Complexité et automates cellulaires linéaires." RAIRO - Theoretical Informatics and Applications 34.5 (2010): 403-423. <http://eudml.org/doc/222081>.

@article{Berthé2010,
abstract = { The aim of this paper is to evaluate the growth order of the complexity function (in rectangles) for two-dimensional sequences generated by a linear cellular automaton with coefficients in $\mathbb\{Z\}/l \mathbb\{Z\}$, and polynomial initial condition. We prove that the complexity function is quadratic when l is a prime and that it increases with respect to the number of distinct prime factors of l. },
author = {Berthé, Valérie},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {linear cellular automaton},
language = {fre},
month = {3},
number = {5},
pages = {403-423},
publisher = {EDP Sciences},
title = {Complexité et automates cellulaires linéaires},
url = {http://eudml.org/doc/222081},
volume = {34},
year = {2010},
}

TY - JOUR
AU - Berthé, Valérie
TI - Complexité et automates cellulaires linéaires
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 5
SP - 403
EP - 423
AB - The aim of this paper is to evaluate the growth order of the complexity function (in rectangles) for two-dimensional sequences generated by a linear cellular automaton with coefficients in $\mathbb{Z}/l \mathbb{Z}$, and polynomial initial condition. We prove that the complexity function is quadratic when l is a prime and that it increases with respect to the number of distinct prime factors of l.
LA - fre
KW - linear cellular automaton
UR - http://eudml.org/doc/222081
ER -

References

top
  1. J.-P. Allouche, Automates finis en théorie des nombres. Exposition. Math.5 (1987) 239-266.  
  2. J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc.1 (1994) 133-143.  
  3. J.-P. Allouche et V. Berthé, Triangle de Pascal, complexité et automates. Bull. Belg. Math. Soc.4 (1997) 1-23.  
  4. J.-P. Allouche et J. Shallit, The ring of k-regular sequences. Theoret. Comput. Sci.98 (1992) 163-197.  
  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. Fractals3 (1995) 663-677.  
  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 (1996) 1-22.  
  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.  
  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.  
  10. F. Blanchard, P. Kurka et A. Maass, Topological and measure-theoretic properties of one-dimensional cellular automata. Phys. D103 (1997) 86-99.  
  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.  
  12. A. Cobham, Uniform tag sequences. Math. Systems Theory6 (1972) 164-192.  
  13. C. Grillenberger, Construction of striclty ergodic systems I. Given entropy. Z. Wahrsch. Verw. Gebiete25 (1973) 323-334.  
  14. B. Litow et P. Dumas, Additive cellular automata and algebraic series. Theoret. Comput. Sci.119 (1993) 345-354.  
  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.  
  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.  
  17. G. Manzini et L. Margara, Invertible cellular automata over ℤ m : Algorithmic and dynamical aspects. J. Comput. System Sci.56 (1998) 60-67.  
  18. G. Manzini et L. Margara, A complete and efficiently computable topological classification of D-dimensional linear cellular automata over ℤ m . Theoret. Comput. Sci.221 (1999) 157-177.  
  19. O. Martin, A. Odlyzko et S. Wolfram, Algebraic properties of cellular automata. Comm. Math. Phys.93 (1984) 219-258.  
  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.  
  21. A.D. Robinson, Fast computation of additive cellular automata. Complex Systems1 (1987) 211-216.  
  22. O. Salon, Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris Sér. I Math.305 (1987) 501-504.  
  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.  
  24. J.W. Sander, R. Tijdeman, The complexity of functions on lattices. Theoret. Comput. Sci. (à paraître).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.