聖塔非研究所
應用 De Bruijn 圖計算一維元胞自動機中的顯式原像
2026-03-18 · 工作論文 · 更新 2026/03/18 下午04:22
摘要 本文展示如何簡化元胞自動機中原像的計算。此方法基於所謂的 De Bruijn 圖，適用於一維空間中的任何 k 狀態和 r 半徑。為了計算原像，我們從 De Bruijn 圖建構原像矩陣以及在這些矩陣上定義的運算子。這樣，計算原像的問題就簡化為解決圖論中經典的“路徑查找問題”，其中所有可能的路徑都是元胞自動機的原像。
本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #525
- 日期：2026-03-18
摘要
本文展示如何簡化元胞自動機中原像的計算。此方法基於所謂的 De Bruijn 圖，適用於一維空間中的任何 k 狀態和 r 半徑。為了計算原像，我們從 De Bruijn 圖建構原像矩陣以及在這些矩陣上定義的運算子。這樣，計算原像的問題就簡化為解決圖論中經典的“路徑查找問題”，其中所有可能的路徑都是元胞自動機的原像。