Complexité et automates cellulaires linéaires
Valérie Berthé (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
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 is a prime and that it increases with respect to the number of distinct prime factors of .