摘要 在元胞自動機和迭代地圖等動態系統中，查看系統產生的語言或符號序列集通常很有用

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

• SFI 頁面

論文資訊

• 類型：已發表論文
• 日期：2022-09-02

摘要

在元胞自動機和迭代地圖等動態系統中，查看系統產生的語言或符號序列集通常很有用。有一些完善的分類方案，例如喬姆斯基層次結構，我們可以用它來衡量這些序列集的複雜性，從而衡量產生它們的系統的複雜性。在本文中，我們將研究兩個或更多 di]<-- 輸入 X 來訂購文章 (TGA: 101ED 00004) ISSN: 0022-4715 -------- 概念模式的複雜性層次結構的前幾個級別。我們表明，在 d = 1 中等效的「常規語言」或「局部規則」的幾個定義導致 d 大於或等於 2 中的不同類別。我們探討了這些類別的閉包屬性和計算複雜性，包括不可判定性以及 L、NL 和 NP 完整性結果。我們將這些類別應用於元胞自動機，特別是它們的固定點和週期點集、有限時間影像和極限集。我們證明，d 大於或等於 2 中的 CA 是否具有給定週期的周期點是不可判定的，並且某些「局部格語言」不是任何 CA 的有限時間圖像或極限集。我們還表明，d 維 CA 的有限時間影像的熵不能比 t(-d) 下降得更快，除非它將每個初始條件映射到單一齊次狀態。