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.  Zbl0641.10041
  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.  Zbl0774.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. Fractals3 (1995) 663-677.  Zbl0879.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 (1996) 1-22.  Zbl0854.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.  Zbl0943.11020
  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.11020
  10. F. Blanchard, P. Kurka et A. Maass, Topological and measure-theoretic properties of one-dimensional cellular automata. Phys. D103 (1997) 86-99.  Zbl1194.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.  Zbl1096.68690
  12. A. Cobham, Uniform tag sequences. Math. Systems Theory6 (1972) 164-192.  Zbl0253.02029
  13. C. Grillenberger, Construction of striclty ergodic systems I. Given entropy. Z. Wahrsch. Verw. Gebiete25 (1973) 323-334.  Zbl0253.28004
  14. B. Litow et P. Dumas, Additive cellular automata and algebraic series. Theoret. Comput. Sci.119 (1993) 345-354.  Zbl0787.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.  Zbl0918.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.  Zbl0894.68098
  17. G. Manzini et L. Margara, Invertible cellular automata over m : Algorithmic and dynamical aspects. J. Comput. System Sci.56 (1998) 60-67.  Zbl0914.68144
  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.  Zbl0930.68090
  19. O. Martin, A. Odlyzko et S. Wolfram, Algebraic properties of cellular automata. Comm. Math. Phys.93 (1984) 219-258.  Zbl0564.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.  Zbl0554.68053
  21. A.D. Robinson, Fast computation of additive cellular automata. Complex Systems1 (1987) 211-216.  Zbl0655.68064
  22. O. Salon, Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris Sér. I Math.305 (1987) 501-504.  Zbl0628.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.  
  24. J.W. Sander, R. Tijdeman, The complexity of functions on lattices. Theoret. Comput. Sci. (à paraître).  Zbl1005.68118

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.