首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Reversibility Problem of Multidimensional Finite Cellular Automata
Authors:Chih-Hung Chang  Jing-Yi Su  Hasan Akın  Ferhat Şah
Institution:1.Department of Applied Mathematics,National University of Kaohsiung,Kaohsiung,Taiwan, ROC;2.Cankaya-Ankara,Turkey;3.Department of Mathematics,Ad?yaman University,Ad?yaman,Turkey
Abstract:While the reversibility of multidimensional cellular automata is undecidable and there exists a criterion for determining if a multidimensional linear cellular automaton is reversible, there are only a few results about the reversibility problem of multidimensional linear cellular automata under boundary conditions. This work proposes a criterion for testing the reversibility of a multidimensional linear cellular automaton under null boundary condition and an algorithm for the computation of its reverse, if it exists. The investigation of the dynamical behavior of a multidimensional linear cellular automaton under null boundary condition is equivalent to elucidating the properties of the block Toeplitz matrix. The proposed criterion significantly reduces the computational cost whenever the number of cells or the dimension is large; the discussion can also apply to cellular automata under periodic boundary conditions with a minor modification.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号