二叉树型结构的细胞自动机同构性构造

摘要：

用状态转移矩阵方程表示加性细胞自动机的状态转移,通过状态转移矩阵及其特征多项式来分析加性细胞自动机的状态转移特性,从而求出其状态转移图.2k-1单元的零边界90线性细胞自动机的状态转移矩阵的秩为2k-2,从而可以确定其状态转移图具有二叉树型结构.同时,根据其状态转移矩阵方程可以求出2k-1单元的零边界90线性细胞自动机对应的22k-1个2k-1单元的零边界90加性细胞自动机具有相同的状态转移结构,即这22k-1个90加性细胞自动机同构.这样可系统构造一簇具有相同二叉树型状态转移结构的细胞自动机.

关键词：细胞自动机、状态转移图、二叉树、同构

所属期刊栏目：35

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金60603009

在线出版日期：2008-06-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：184-185,189