Group Properties of Non-linear Cellular Automata
Debdeep Mukhopadhyay
The paper studies the group properties exhibited by Non-linear Cellular Automaton (NCA). The paper describes a method to combine small nonlinear, invertible machines with group linear Cellular Automaton (CA) to obtain large non-linear machines with predictable cyclic structures.We show with large number of experimental results that through proper choice of the rules of the linear CA we may obtain highly non-linear invertible mappings without affecting the group properties of the linear CA. We also study a class of non-linear CA, with OR-gates to realize their transition functions. In order to predict the group properties of the CA we develop a method using the graphical representation of its transition matrix.We prove that the graph of the transition matrix of an OR-NCA (OR based Non-linear CA) which forms a group does not have certain forbidden patterns. The proposed prediction of the group properties of the OR-NCAis much faster than an exhaustive simulation of the machine.
Keywords: Combinatorial problems, non-linear cellular automata, group cellular automata