Structure and reversibility of 2D hexagonal cellular automata

被引:32
作者
Siap, Irfan [1 ]
Akin, Hasan [2 ]
Uguz, Selman [3 ]
机构
[1] Yildiz Tech Univ, Dept Math, Arts & Sci Fac, Istanbul, Turkey
[2] Zirve Univ, Fac Educ, Dept Math, TR-27260 Gaziantep, Turkey
[3] Harran Univ, Arts & Sci Fac, Dept Math, TR-63120 Sanliurfa, Turkey
关键词
Hexagonal cellular automata; Rule matrix; Reversible cellular automata; Matrix algebra; CRYPTOGRAPHY; RULES;
D O I
10.1016/j.camwa.2011.09.066
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Cellular automata are used to model dynamical phenomena by focusing on their local behavior which depends on the neighboring cells in order to express their global behavior. The geometrical structure of the models suggests the algebraic structure of cellular automata. After modeling the dynamical phenomena, it is sometimes an important problem to be able to move backwards in order to understand it better. This is only possible if cellular automata is reversible. In this paper, 2D finite cellular automata defined by local rules based on hexagonal cell structure are studied. Rule matrix of the hexagonal Finite cellular automaton is obtained. The rank of rule matrices representing the 20 hexagonal finite cellular automata via an algorithm is computed. It is a well known fact that determining the reversibility of a 2D cellular automata is a very difficult problem in general. Here, the reversibility problem of this family of 2D hexagonal cellular automata is also resolved completely. (C) 2011 Elsevier Ltd. All rights reserved.
引用
收藏
页码:4161 / 4169
页数:9
相关论文
共 26 条
[1]  
Adamatzky A., 2006, CHAOS SOLITON FRACT, V27
[2]   On cellular automata over Galois rings [J].
Akin, Hasan ;
Siap, Irfan .
INFORMATION PROCESSING LETTERS, 2007, 103 (01) :24-27
[3]  
Akin H, 2010, AIP CONF PROC, V1309, P16, DOI 10.1063/1.3525111
[4]   A multisecret sharing scheme for color images based on cellular automata [J].
Alvarez, G. ;
Encinas, L. Hernandez ;
del Rey, A. Martin .
INFORMATION SCIENCES, 2008, 178 (22) :4382-4395
[5]   Theory and applications of cellular automata in cryptography - Comment [J].
Blackburn, SR ;
Murphy, S ;
Paterson, KG .
IEEE TRANSACTIONS ON COMPUTERS, 1997, 46 (05) :637-638
[6]   Characterisation of a particular hybrid transformation of two-dimensional cellular automata [J].
Chattopadhyay, P ;
Choudhury, PP ;
Dihidar, K .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1999, 38 (5-6) :207-216
[7]  
D'Ambrosio D., 2003, NAT HAZARD EARTH SYS, V3
[8]  
Das A.K., 1990, THESIS IIT KHARAGPHU
[9]   Matrix algebraic formulae concerning some exceptional rules of two-dimensional cellular automata [J].
Dihidar, K ;
Choudhury, PP .
INFORMATION SCIENCES, 2004, 165 (1-2) :91-101
[10]   INVERSION OF 2D CELLULAR-AUTOMATA - SOME COMPLEXITY RESULTS [J].
DURAND, B .
THEORETICAL COMPUTER SCIENCE, 1994, 134 (02) :387-401