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

This paper investigates a variant of cellular automata, namely ν-CA. Indeed, ν-CA are cellular automata which can have dierent 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-innite words. The complexity classes of these languages are investigated providing an initial rough classica-tion of ν-CA.