dorsal/arxiv
View SchemaPredicting Non-linear Cellular Automata Quickly by Decomposing Them into Linear Ones
| Authors | Cristopher Moore |
|---|---|
| Categories | |
| ArXiv ID | patt-sol/9701008 |
| URL | https://arxiv.org/abs/patt-sol/9701008 |
| DOI | 10.1016/S0167-2789(97)80003-6 |
Abstract
We show that a wide variety of non-linear 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 are allowed. Thus these CAs can be predicted by (idealized) parallel computers much faster than by explicit simulation, even though they are non-linear. This class includes any CA whose rule, when written as an algebra, is a solvable group. We also show that CAs based on nilpotent groups can be predicted in depth O(log t) or O(1) by circuits with binary or ``sum mod p'' gates respectively. We use these techniques to give an efficient algorithm for a CA rule which, like elementary CA rule 18, has diffusing defects that annihilate in pairs. This can be used to predict the motion of defects in rule 18 in O(log^2 t) parallel time.
{
"annotation_id": "f6b69f3a-035d-41f5-b79f-883853ad3b27",
"date_created": "2026-03-02T18:00:28.859000Z",
"date_modified": "2026-03-02T18:00:28.859000Z",
"file_hash": "7fe77ba924d9c2bcc0c966ce3f63a259709d30786c34dbdafb43c743396c9696",
"private": false,
"record": {
"abstract": "We show that a wide variety of non-linear cellular automata (CAs) can be\ndecomposed into a quasidirect product of linear ones. These CAs can be\npredicted by parallel circuits of depth O(log^2 t) using gates with binary\ninputs, or O(log t) depth if ``sum mod p\u0027\u0027 gates with an unbounded number of\ninputs are allowed. Thus these CAs can be predicted by (idealized) parallel\ncomputers much faster than by explicit simulation, even though they are\nnon-linear.\n This class includes any CA whose rule, when written as an algebra, is a\nsolvable group. We also show that CAs based on nilpotent groups can be\npredicted in depth O(log t) or O(1) by circuits with binary or ``sum mod p\u0027\u0027\ngates respectively.\n We use these techniques to give an efficient algorithm for a CA rule which,\nlike elementary CA rule 18, has diffusing defects that annihilate in pairs.\nThis can be used to predict the motion of defects in rule 18 in O(log^2 t)\nparallel time.",
"arxiv_id": "patt-sol/9701008",
"authors": [
"Cristopher Moore"
],
"categories": [
"patt-sol",
"adap-org",
"comp-gas",
"nlin.AO",
"nlin.CG",
"nlin.PS"
],
"doi": "10.1016/S0167-2789(97)80003-6",
"title": "Predicting Non-linear Cellular Automata Quickly by Decomposing Them into Linear Ones",
"url": "https://arxiv.org/abs/patt-sol/9701008"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "185d98b5-819f-4698-89cf-066d09568d2e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}