Logical Model of Cellular Automata

This paper introduces a logic language L-CA as a model of one-dimensional d-state m-neighborhood cellular automata (CAs) with d , m >= 2. We first develop the syntax of L-CA , and then semantics are given to L-CA in the domain of all d-ary strings. It is shown that the finite CAs of any d and m are models of the proposed logic language under any boundary condition. Classical CAs, which are defined over an infinite lattice, are also shown to be models of L-CA under two popular classes of configurations: finite and periodic. The proposed logical model further guides us to develop a new class of CAs, which we name homoasynchronous CAs, where a group of (nearby) cells with homogeneous configurations can be updated independently during evolution.