Local rule distributions, language complexity and non-uniform cellular automata.

Abstract: This paper investigates a variant of cellular automata, namely -CA. Indeed, -CA are cellular automata which can have different local rules at each site of their lattice. The assignment of local rules to sites of the lattice completely characterizes -CA. In this paper, sets of assignments sharing some interesting properties are associated with languages of bi-infinite words. The complexity classes of these languages are investigated providing an initial rough classification of -CA. [Copyright &y& Elsevier]