Investigation of the global dynamics of cellular automata using Boolean derivatives

• Published in: Computers & mathematics with applications (1987) 2009-04, Vol.57 (8), p.1337-1351
• Main Authors: Choudhury, Pabitra Pal, Sahoo, Sudhakar, Chakraborty, Mithun, Bhandari, Subir Kumar, Pal, Amita
• Format: Article
• Language: English
• Subjects: Algebraic normal form; Boolean functions; Error function; Jacobian matrix; Linear and affine functions; Modified Jacobian matrix; State transition diagram; Wolfram’s naming scheme
• ISSN: 0898-1221; 1873-7668
• DOI: 10.1016/j.camwa.2008.11.012

Global dynamics of a non-linear Cellular Automaton (CA), is, in general irregular, asymmetric and unpredictable as opposed to that of a linear CA, which is highly systematic and tractable. In this paper, efforts have been made to systematize non-linear CA evolutions in the light of Boolean derivatives and Jacobian matrices. A few new theorems on Hamming Distance between Boolean functions as well as on Jacobian matrices of cellular automata are proposed and proved. Moreover, a classification of Boolean functions based on the nature of deviation from linearity has been suggested with a view to grouping them together to classes/subclasses such that the members of a class/subclass satisfy certain similar properties. Next, an error vector, which cannot be captured by the Jacobian matrix, is identified and systematically classified. This leads us to the concept of modified Jacobian matrix whereby a quasi-affine representation of a non-linear cellular automaton is introduced.