本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #1176
- 日期：2026-03-18
摘要
在元胞自動機和迭代地圖等動態系統中，查看系統產生的「語言」或符號序列集通常很有用。有一些完善的分類方案，例如喬姆斯基層次結構，我們可以用它來衡量這些序列集的複雜性，從而衡量產生它們的系統的複雜性。在本文中，我們研究二維或更多維模式的複雜性層次結構的前幾個層次。我們證明了 $d=1$ 中等價的「常規語言」或「本地規則」的幾個定義導致了 $d\geq 2$ 中不同的類別。我們探索這些類別的閉包屬性和計算複雜性，包括某些不可判定性和 NP 完整性結果。我們將這些類別應用於元胞自動機，特別是它們的固定點和週期點集、有限時間影像和極限集。我們證明 $d \geq 2$ 中的 CA 是否具有給定週期的周期點是不可判定的，並且某些「局部格語言」不是任何 CA 的有限時間圖像或極限集。我們還表明，$d$ 維 CA 的有限時間影像的熵不能比 $t^{-d}$ 下降得更快，除非它將每個初始條件映射到單一齊次狀態。