计算机科学 ›› 2024, Vol. 51 ›› Issue (10): 330-336.doi: 10.11896/jsjkx.240100207
马骏驰, 陈伟霖, 王晨, 林德福, 王超
MA Junchi, CHEN Weilin, WANG Chen, LIN Defu, WANG Chao
摘要： 可逆性的性质对于经典的计算机科学理论模型——细胞自动机(Cellular Automata,CA)具有重要意义。尽管CA在零边界条件下的线性规则的可逆性问题已经得到了大量的研究,但非线性规则目前还很少被探索。文中研究了在有限域$\mathbb{Z}_{p}$上一般一维CA的可逆性问题,找到了一种优化Amoroso无限CA满射性判定算法的方法。基于此,文中还提出了在零边界条件下判定一维CA可逆性的算法,其中包括一种在零边界条件下判定一维CA严格可逆性的算法,以及一种基于桶链的在零边界条件下计算一维CA的可逆性函数的算法。这些判定算法不仅适用于线性规则,也适用于非线性规则。除此以外,还证实了可逆性函数总是有一个周期的,且其周期性与对应桶链的周期性有关。文中给出了一些可逆CA的实验结果,并通过实验结果对理论部分进行了补充验证,进一步支持了文章的研究结论。
中图分类号:
| [1]VON NEUMANN J,BURKS A W.Theory of self-reproducing automata[J].IEEE Transactions on Neural Networks,1966,5(1):3-14. [2]GARDNER M.Mathematical games[J].Scientific American,1970,222(6):132-140. [3]WANG J,LV W,JIANG Y,et al.A cellular automata approach for modelling pedestrian-vehicle mixed traffic flow in urban city[J].Applied Mathematical Modelling,2023,115:1-33. [4]KIPPENBERGER S,BERND A,THAÇI D,et al.Modeling pat-tern formation in skin diseases by a cellular automaton[J].The Journal of Investigative Dermatology,2013,133(2):567. [5]VALENTIM C A,RABI J A.,DAVID S A.Cellular-automaton model for tumor growth dynamics:Virtualization of different scenarios[J].Computers in Biology and Medicine,2022,153:106481. [6]WANG Y,ZHANG L,MA J,et al.Combining building and behavior models for evacuation planning[J].IEEE Computer Graphics and Applications,2010,31(3):42-55. [7]REN F,GE H,FANG H,et al.Simulation of the dendritegrowth during directional solidification under steady magnetic field using three-dimensional cellular automaton method coupled with Eulerian multiphase[J].International Journal of Heat and Mass Transfer,2024,218:124809. [8]ZHOU F,GUO J,ZHAO Y,et al.An improved cellular automaton model of dynamic recrystallization and the constitutive mo-del coupled with dynamic recrystallization kinetics for microalloyed high strength steels[J/OL].https://doi.org/10.1016/j.jmrt.2023.12.024. [9]XU X,FAN C,WANG L.A deep analysis of the image and videoprocessing techniques using nanoscale quantum-dots cellular automata[J].Optik,2022,260:169036. [10]DARANI A Y,YENGEJEH Y K,PAKMANESH H,et al.Image encryption algorithm based on a new 3D chaotic system using cellular automata[J].Chaos,Solitons & Fractals,2024,179:114396. [11]CAPPELLARI L,MILANI S,CRUZ-REYES C,et al.Resolution scalable image coding with reversible cellular automata[J].IEEE Transactions on Image Processing,2010,20(5):1461-1468. [12]MOORE E F.Machine models of self-reproduction[J].Procee-dings of symposia in applied mathematics.American Mathematical Society New York,1962,14(5):17-33. [13]AMOROSO S,PATT Y N.Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures[J].Journal of Computer and System Sciences,1972,6(5):448-464. [14]BRUCKNER L K.On the Garden-of-Eden problem for one-di-mensional cellular automata[J].Acta Cybernetica,1979,4(3):259-262. [15]SUTNER K.De Bruijn graphs and linear cellular automata[J].Complex Systems,1991,5(1):19-30. [16]DEL REY A M.A note on the reversibility of elementary cellular automaton 150 with periodic boundary conditions[J].Romanian Journal of Information Science and Technology,2013,16(4):365-372. [17]DEL REY A M.A note on the reversibility of the elementary cellular automaton with rule number 90[J].Revista De la Unión Matemática Argentina,2015,56(1):107-125. [18]DEL REY A M,SÁNCHEZ G R.On the reversibility of 150 Wolfram cellular automata[J].International Journal of Modern Physics C,2006,17(7):975-983. [19]SARKAR P,BARUA R.The set of reversible 90/150 cellularautomata is regular[J].Discrete Applied Mathematics,1998,84(1／2／3):199-213. [20]CINKIR Z,AKIN H,SIAP I.Reversibility of 1D cellular auto-mata with periodic boundary over finite fields[J].Journal of Statistical Physics,2011,143(4):807-823. [21]YANG B,WANG C,XIANG A.Reversibility of general 1D linearcellular automata over the binary field Z2 under null boundary conditions[J].Information Sciences,2015,324:23-31. [22]DU X,WANG C,WANG T,et al.Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over Zp[J].Information Sciences,2022,594:163-176. [23]WOLFRAM S,GAD-El-HAK M.A new kind of science[J].Ap-pl.Mech.Rev.,2003,56(2):18-19. |
|
||
首页