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

计算机科学 ›› 2008, Vol. 35 ›› Issue (4): 184-185.

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

张传武

西南民族大学电气信息工程学院,成都610041

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
国家自然科学基金项目（资助号60603009）.

ZHANG Chuan-Wu （CEIE, Southwest University for Nationalities, Chengdu 610041 ）

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

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

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

Abstract: The state transition diagram of additive cellular automata can be expressed by the matrix equation. The state transition diagram can be presented by the analysis of state transition matrix and its characteristic polynomial. The rank of 2^k -1 cells null b

Key words: Cellular automata, States transition diagram, Binary tree, Homogeneous characteristic.

张传武. 二叉树型结构的细胞自动机同构性构造[J]. 计算机科学, 2008, 35(4): 184-185. https://doi.org/

ZHANG Chuan-Wu （CEIE, Southwest University for Nationalities, Chengdu 610041 ）. [J]. Computer Science, 2008, 35(4): 184-185. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed