本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：1998
摘要
We show that a wide variety of 非線性 細胞自動機 (CAs) can be decomposed into a quasidirect product of linear ones. These CAs can be predicted by parallel circuits of depth 0(log(2)t) using gates with binary inputs, or 0(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 非線性. 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 0(log t) or 0(1) by circuits with binary or "sum mod p" gates, respectively. We use these techniques to give an efficient algorithm for a CA rulewhich, like elementary CA rule Is, has diffusing defects that ann
※ 此為已發表論文，全文需透過期刊付費取得