本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #1322
- 日期：2026-03-18
摘要
模擬未來 $t$ 時間步長的元胞自動機 (CA) 需要 $t^2$ 序列計算步驟或 $t$ 平行計算步驟。然而，某些基於阿貝爾群的 CA（例如加法 mod 2）被稱為線性，因為它們遵循疊加原理。這使得它們可以在序列時間 ${\cal O} (t)[1]$ 或平行時間 ${\cal O} (\log t)$ 中有效地進行預測。在本文中，我們透過研究具有各種代數結構的 CA 來概括這一點，包括擬群、非阿貝爾群、斯坦納系統和其他結構。我們表明，在許多情況下，即使這些 CA 在先前的意義上不是線性的，但也存在有效的演算法；我們稱它們為擬線性的。我們找到了可以在 $\alpha <2$ 的情況下以與 $t$、$t\log t\log^2$ 和 $t^\alpha$ 成比例的串行時間進行預測的示例，以及並行時間 $\log t$、$log t\log\log t$ 和 $\log^2 t$ 的示例。我們也討論了縮放關係和疊加原理的存在所需或暗示的代數性質，並展示了幾種新穎的「向量值」CA。