| Issue |
RAIRO-Theor. Inf. Appl.
Volume 34, Number 5, September/October 2000
|
|
|---|---|---|
| Page(s) | 403 - 423 | |
| DOI | https://doi.org/10.1051/ita:2000124 | |
| Published online | 15 April 2002 | |
Complexité et automates cellulaires linéaires
IML, UPR 9016, Case 907, 163 avenue de Luminy, 13288 Marseille Cedex 09, France; (berthe@iml.univ-mrs.fr)
Received:
2
March
2000
Accepted:
18
October
2000
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 
, 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.
Résumé
Le but de cet article est d'évaluer l'ordre de croissance
de la fonction de complexité rectangulaire de suites doubles engendrées
par un automate cellulaire linéaire à coefficients
dans et à condition initiale
polynomiale.
On montre que la fonction de complexité
est quadratique quand l est un nombre premier et qu'elle
croît en proportion du nombre de facteurs premiers distincts de l.
Mathematics Subject Classification: 68R15 / 11B85 / 68Q80 / 05A10
© EDP Sciences, 2000
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.