Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T20:20:06.082Z Has data issue: false hasContentIssue false

Complexité et automates cellulaires linéaires

Published online by Cambridge University Press:  15 April 2002

Valérie Berthé*
Affiliation:
IML, UPR 9016, Case 907, 163 avenue de Luminy, 13288 Marseille Cedex 09, France; (berthe@iml.univ-mrs.fr)
Get access

Abstract

The aim of this paper is to evaluate the growth orderof the complexity function (in rectangles)for two-dimensional sequencesgenerated by a linear cellular automatonwith coefficients in $\mathbb{Z}/l \mathbb{Z}$ , and polynomial initial condition.We prove that the complexity functionis quadratic when l is a prime and that it increases with respect to the number of distinct prime factors of l.

Keywords

Information

Type
Research Article
Copyright
© EDP Sciences, 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable