Predicting nonlinear cellular automata q
โ
Cristopher Moore
๐
Article
๐
1998
๐
Elsevier Science
๐
English
โ 850 KB
We show that a wide variety of nonlinear cellular automata (CAs) can be decomposed into a quasidirect product of linear ones. These CAs can be predicted by parallel circuits of depth O(log 2 t) using gates with binary inputs, or O(log t) depth if "sum mod p" gates with an unbounded number of inputs