Language Recognition by Cellular Automata

International audienceCellular automata (CA) comprise a simple and well-formalized model of massively parallel computation, which is known to be capable of universal computation. Because of their parallel behavior, CA have rich abilities of information processing; however, it is not easy to define their power limitations. A convenient approach to characterizing the computation capacity of CA is to investigate their complexity classes. This chapter discusses the CA complexity classes and their relationships with other models of computations