零边界条件下一维非线性细胞自动机可逆性的判定算法  

Decision Algorithms for Reversibility of One-dimensional Non-linear Cellular Automata Under Null Boundary Conditions

作　　者：马骏驰 陈伟霖 王晨 林德福 王超[1] MA Junchi;CHEN Weilin;WANG Chen;LIN Defu;WANG Chao(College of Software,Nankai University,Tianjin 300350,China)

机构地区：[1]南开大学软件学院,天津300350

出　　处：《计算机科学》2024年第10期330-336,共7页Computer Science

基　　金：天津市自然科学基金(21JCYBJC00210)。

摘　　要：可逆性的性质对于经典的计算机科学理论模型——细胞自动机(Cellular Automata,CA)具有重要意义。尽管CA在零边界条件下的线性规则的可逆性问题已经得到了大量的研究,但非线性规则目前还很少被探索。文中研究了在有限域Z_(p)上一般一维CA的可逆性问题,找到了一种优化Amoroso无限CA满射性判定算法的方法。基于此,文中还提出了在零边界条件下判定一维CA可逆性的算法,其中包括一种在零边界条件下判定一维CA严格可逆性的算法,以及一种基于桶链的在零边界条件下计算一维CA的可逆性函数的算法。这些判定算法不仅适用于线性规则,也适用于非线性规则。除此以外,还证实了可逆性函数总是有一个周期的,且其周期性与对应桶链的周期性有关。文中给出了一些可逆CA的实验结果,并通过实验结果对理论部分进行了补充验证,进一步支持了文章的研究结论。The property of reversibility is quite meaningful for the classic theoretical computer science model,cellular automata.For the reversibility problem for a CA under null boundary conditions,while linear rules have been extensively studied,the non-linear rules have so far been rarely explored.The paper investigates the reversibility problem of general one-dimensional CA on a finite field Z_(p),and proposes an approach to optimize the Amoroso’s infinite CA surjectivity detection algorithm.Based on this,this paper proposes an algorithm for determining the invertibility of one-dimensional CA under zero boundary conditions,including an algorithm for determining the strict invertibility of one-dimensional CA under zero boundary conditions,and an algorithm for calculating the invertibility function of one-dimensional CA under zero boundary conditions based on barrel chain.These decision algorithms work for not only linear rules but also non-linear rules.In addition,it has been confirmed that the reversibility function always has a period,and its periodicity is related to the periodicity of the corresponding bucket chain.Some of the experiment results of reversible CA are presented in this paper,complementing and validating the theoretical aspects,and thereby further supporting the research conclusions of this paper.

关 键 词：细胞自动机 非线性规则 可逆性 零边界 一维 

分 类 号：TP305[自动化与计算机技术—计算机系统结构]