聖塔非研究所 Non-Abelian 細胞自動機 2026-03-18 · 工作論文 · 更新 2026/03/19 上午12:17 摘要 我們證明了各種各樣的非線性元胞自動機可以寫成線性元胞自動機的“半直積”，並且這些 CA 可以在並行時間 ${\cal O}(\log^2t)$ 內進行預測。此類別包括任何 CA，其規則在寫為代數時是可解群。我們還表明，透過對換向器水平的歸納，可以在並行時間 ${\cal O}(\log t)$ 中預測基於冪零群的 CA。 原文連結PDF 來源 本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。 原文連結 原文連結 PDF 來源 論文資訊 類型：工作論文 編號：工作論文 #1324 日期：2026-03-18 摘要 我們證明了各種各樣的非線性元胞自動機可以寫成線性元胞自動機的“半直積”，並且這些 CA 可以在並行時間 ${\cal O}(\log^2t)$ 內進行預測。此類別包括任何 CA，其規則在寫為代數時是可解群。我們還表明，透過對換向器水平的歸納，可以在並行時間 ${\cal O}(\log t)$ 中預測基於冪零群的 CA。