線性細胞自動機的可逆性研究.pdf

1、細胞自動機(Cellular Automata)是離散的和確定性的動態(tài)系統(tǒng)，它們尤其適合用于建模與仿真，可以被描述為簡單的對象彼此局部相互作用的龐大集合的自然系統(tǒng)。近幾年來，細胞自動機已經廣泛應用在科學的各個分支，如物理學(生長過程模型）、生物學(自我繁殖模型、生物結構等）、信息科學(圖像處理、糾錯碼、密碼學等）。
　　在一維細胞自動機方面，目前在零邊界、反射邊界和周期邊界條件下，一維線性細胞自動機的可逆性已經取得了一些成果，但是

2、許多已有研究工作都是針對特定的某些線性規(guī)則，難以做到判定任意線性規(guī)則的可逆性。本文創(chuàng)新性地引入De Bruijn圖這一強大工具，可以在零邊界條件下快速確定任意一維線性細胞自動機的可逆性，并且可以推廣到有限狀態(tài)域Fp上。
　　在二維細胞自動機方面，Kari等人證明了二維或高維細胞自動機在全局的可逆性是不可判定問題。本文探究了零邊界條件下二維線性細胞自動機的可逆性，通過實驗給出了整體可逆的二維線性CA和整體不可逆的二維線性CA所需要滿