Structure and reversibility of 2D hexagonal cellular automata

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 2D 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.     

Dynamical characteristics of linear cellular automata

Dynamical characteristics of linear cellular automata are discussed algebraically, whose cell space and state space are an Abelian group and a finite commutative ring, respectively, instead of a lattice space and a residue class. One of the main results is a characterization of the dynamical structures with relation to what the unit configuration is. It is also shown that a linear cellular automaton with the state space of a residue class of an integer m can be decomposed in parallel into automata with the one of a power of a prime which is a factor of m. Using those results, the proofs of known results are improved concerning C-surjectivity, C-injectivity, and finite-order property for linear cellular automata and presented in a unified manner.     

Analysis of bounded linear cellular automata based on a method of image charges

The temporal evolution of a class of one-dimensional cellular automata (CA) implementable in VLSI, is a problem of considerable complexity in the presence of the natural (null) boundary conditions. This paper provides an analytical solution to their evolution, based upon a method of image charges borrowed from electrostatics. Reductions in computational effort by factors of O(L²) for a single site value, or O(L) for the entire configuration of the CA, as compared to direct simulation, are obtainable by the present method of image charges. These results are expected to provide a basis for CA applications as highly parallel computational structures to be incorporated as functional blocks is novel VLSI architectures.     

On real-time cellular automata and trellis automata

Summary It is shown that f(n)-time one-way cellular automata are equivalent to f(n)-time trellis automata, the real-time one-way cellular automata languages are closed under reversal, the 2n-time one-way cellular automata are equivalent to real-time cellular automata and the latter are strictly more powerful than the real-time one-way cellular automata.This work has been done during the second author's visit at the University of Paris and during both authors' visit at the Institute für Informationsverarbeitung Graz, Austria     

基于混沌和细胞自动机的图像加密算法

为了设计加密性能好、容易实现的加密系统,充分利用混沌系统的密码学特性和细胞自动机良好的加密性能,提出了一种基于混沌系统和触发细胞自动机的图像加密算法.算法先利用混沌序列对图像进行加密处理;通过构造反转规则建立触发细胞自动机,并根据触发细胞自动机的迭代规则对图像进行二次加密.加密过程简单高效,且具有较大的密钥空间,可以保证系统的安全性.实验结果表明,该算法具有较好的加解密性能,且较小的邻域半径即可得到良好的加密效果,因此非常便于硬件实现.     

Hyperspectral image segmentation through evolved cellular automata

Segmenting multidimensional images, in particular hyperspectral images, is still an open subject. Two are the most important issues in this field. On one hand, most methods do not preserve the multidimensional character of the signals throughout the segmentation process. They usually perform an early projection of the hyperspectral information to a two dimensional representation with the consequent loss of the large amount of spectral information these images provide. On the other hand, there is usually very little and dubious ground truth available, making it very hard to train and tune appropriate segmentation and classification strategies. This paper describes an approach to the problem of segmenting and classifying regions in multidimensional images that performs a joint two-step process. The first step is based on the application of cellular automata (CA) and their emergent behavior over the hyperspectral cube in order to produce homogeneous regions. The second step employs a more traditional SVM in order to provide labels for these regions to classify them. The use of cellular automata for segmentation in hyperspectral images is not new, but most approaches to this problem involve hand designing the rules for the automata and, in general, average out the spectral information present. The main contribution of this paper is the study of the application of evolutionary methods to produce the CA rule sets that result in the best possible segmentation properties under different circumstances without resorting to any form of projection until the information is presented to the user. In addition, we show that the evolution process we propose to obtain the rules can be carried out over RGB images and then the resulting automata can be used to process multidimensional hyperspectral images successfully, thus avoiding the problem of lack of appropriately labeled ground truth images. The procedure has been tested over synthetic and real hyperspectral images and the results are very competitive.     

Parallel image processing by memory-augmented cellular automata

This paper introduces a generalization of cellular automata in which each celi is a tape-bounded Turing machine rather than a finite-state machine. Fast algorithms are given for performing various basic image processing tasks by such automata. It is suggested that this model of parallel computation is a very suitable one for studying the advantages of parallelism in this domain.     

On the ergodic theory of cellular automata

When properly viewed, the transition rule of a cellular automaton becomes a mapF from a set to itself. The set may be made a probability space. Sufficient conditions are given to ensure thatF be measure-preserving and ergodic. Some geometric consequences of ergodicity are noted.     

On computing the entropy of cellular automata

We study the topological entropy of a particular class of dynamical systems: cellular automata. The topological entropy of a dynamical system (X,F) is a measure of the complexity of the dynamics of F over the space X. The problem of computing (or even approximating) the topological entropy of a given cellular automata is algorithmically undecidable (Ergodic Theory Dynamical Systems 12 (1992) 255). In this paper, we show how to compute the entropy of two important classes of cellular automata namely, linear and positively expansive cellular automata. In particular, we prove a closed formula for the topological entropy of D-dimensional (D1) linear cellular automata over the ring Z_m (m2) and we provide an algorithm for computing the topological entropy of positively expansive cellular automata.     

On time-symmetry in cellular automata

The notion of reversibility has been intensively studied in the field of cellular automata (CA), for several reasons. However, a related notion found in physical theories has been so far neglected, not only in CA, but generally in discrete dynamical systems. This is the notion of time-symmetry, which refers to the inability of distinguishing between backward and forward time directions. Here we formalize it in the context of CA, and study some of its basic properties. We also show how some well-known CA fit into the class of time-symmetric CA, and provide a number of results on the relation between this and other classes of CA. The existence of an intrinsically universal time-symmetric CA within the class of reversible CA is proved. Finally, we show the undecidability of time-symmetry for CA of dimension 2 or higher, even within the class of reversible CA. The case of dimension 1 is one of several open questions discussed in the conclusions.     

Secret image sharing based on cellular automata and steganography

Recently Lin and Tsai [Secret image sharing with steganography and authentication, The Journal of Systems and Software 73 (2004) 405-414] and Yang et al. [Improvements of image sharing with steganography and authentication, The Journal of Systems and Software 80 (2007) 1070-1076] proposed secret image sharing schemes combining steganography and authentication based on Shamir's polynomials. The schemes divide a secret image into some shadows which are then embedded in cover images in order to produce stego images for distributing among participants. To achieve better authentication ability Chang et al. [Sharing secrets in stego images with authentication, Pattern Recognition 41 (2008) 3130-3137] proposed in 2008 an improved scheme which enhances the visual quality of the stego images as well and the probability of successful verification for a fake stego block is 1/16.In this paper, we employ linear cellular automata, digital signatures, and hash functions to propose a novel (t,n)-threshold image sharing scheme with steganographic properties in which a double authentication mechanism is introduced which can detect tampering with probability 255/256. Employing cellular automata instead of Shamir's polynomials not only improves computational complexity from to O(n) but obviates the need to modify pixels of cover images unnecessarily. Compared to previous methods [C. Lin, W. Tsai, Secret image sharing with steganography and authentication, The Journal of Systems and Software 73 (2004) 405-414; C. Yang, T. Chen, K. Yu, C. Wang, Improvements of image sharing with steganography and authentication, The Journal of Systems and Software 80 (2007) 1070-1076; C. Chang, Y. Hsieh, C. Lin, Sharing secrets in stego images with authentication, Pattern Recognition 41 (2008) 3130-3137], we use fewer number of bits in each pixel of cover images for embedding data so that a better visual quality is guaranteed. We further present some experimental results.     

Digital image scrambling based on elementary cellular automata

Image scrambling is the process of converting an image to an unintelligible format, mainly for security reasons. The scrambling is considered as a pre-process or a post-process of security related applications such as watermarking, information hiding, fingerprinting, and encryption. Cellular automata are parallel models of computation that prove an interesting concept where a simple configuration can lead to a complex behavior. Since there are a lot of parameters to configure, cellular automata have many types and these types differ in terms of complexity and behavior. Cellular automata were previously used in scrambling different types of multimedia, but only complex two-dimensional automata were explored. We propose a scheme where the simplest type of cellular automata is used that is the elementary type. We test the scrambling degree for different cellular automata rules that belong to classes three and four of Wolfram’s classification which correspond to complex and chaotic behavior; we also check the effect of other parameters such as the number of generations and the boundary condition. Experimental results show that our proposed scheme outperforms other schemes based on cellular automata in terms of scrambling degree.     

On the computational power of totalistic cellular automata

Totalistic cellular automata, introduced by S. Wolfram, are cellular automata in which the state transition function depends only on the sum of the states in a cell's neighborhood. Each state is considered as a nonnegative integer and the sum includes the cell's own state. It is shown that one-dimensional totalistic cellular automata can simulate an arbitrary Turing machine in linear time, even when the neighborhood is restricted to one cell on each side. This result settles Wolfram's conjecture that totalistic cellular automata are computation-universal.Research performed while visiting the Department of Computer Science, University of Cincinnati, 1984/85.     

On the directional dynamics of additive cellular automata

We continue the study of cellular automata (CA) directional dynamics, i.e. , the behavior of the joint action of CA and shift maps. This notion has been investigated for general CA in the case of expansive dynamics by Boyle and Lind; and by Sablik for sensitivity and equicontinuity. In this paper we give a detailed classification for the class of additive CA providing non-trivial examples for some classes of Sablik’s classification. Moreover, we extend the directional dynamics studies by considering also factor languages and attractors.     

On cellular automata over Galois rings

In this paper we study the invertibility of one-dimensional cellular automata, determined by a local rule, acting on the space of all doubly-infinite sequences taking values in a finite Galois ring. We also compute the topological entropy of one-dimensional CA generated by additive local rule over a finite Galois ring. We conclude by showing that the topological entropy of an additive invertible CA over a finite Galois ring is equal to its inverse.     

基于混沌细胞自动机的图像加密算法

提出了基于耦合混沌和触发细胞自动机的图像加密算法。首先用耦合混沌系统对图像进行加密,然后用耦合二维细胞自动机再次加密,最后用混沌序列对图像进行置乱。加密过程中同时运用了分组加密和流加密方法。仿真实验结果表明,该加密算法实现简单,扩散和混淆效果比较理想,有较强的抗攻击能力,具有良好的加密效果。     

基于耦合混沌系统和细胞自动机的图像加密算法

提出一种基于耦合混沌系统和细胞自动机的加密方法。耦合混沌系统比单一混沌系统具有更复杂的动力学特性,可以增大密钥空间,提高加密系统的安全性;利用耦合触发细胞自动机实现明文分块的并行加密,提高加/解密速度,改进置乱效果。加密时首先经过混沌加密,然后利用混沌序列产生反转规则,由细胞自动机再次加密;解密过程正好相反。实验表明,这种混合加密方法具有更大的密钥空间和更好的置乱效果,能够有效抵抗蛮力攻击和差分分析攻击。     

On the relationship between fuzzy and Boolean cellular automata

Fuzzy cellular automata (FCA) are continuous cellular automata where the local rule is defined as the “fuzzification” of the local rule of a corresponding Boolean cellular automaton in disjunctive normal form. In this paper, we are interested in the relationship between Boolean and fuzzy models and, for the first time, we analytically show the existence of a strong connection between them by focusing on two properties: density conservation and additivity.We begin by showing that the density conservation property, extensively studied in the Boolean domain, is preserved in the fuzzy domain: a Boolean CA is density conserving if and only if the corresponding FCA is sum preserving. A similar result is established for another novel “spatial” density conservation property. Second, we prove an interesting parallel between the additivity of Boolean CA and oscillations of the corresponding fuzzy CA around its fixed point. In fact, we show that a Boolean CA is additive if and only if the behaviour of the corresponding fuzzy CA around its fixed point coincides with the Boolean behaviour. Finally, we give a probabilistic interpretation of our fuzzification which establishes an equivalence between convergent fuzzy CA and the mean field approximation on Boolean CA, an estimation of their asymptotic density.These connections between the Boolean and the fuzzy models are the first formal proofs of a relationship between them.