Some applications of propositional logic to cellular automata

In this paper we give a new proof of Richardson's theorem [31]: a global function G_?? of a cellular automaton ?? is injective if and only if the inverse of G_?? is a global function of a cellular automaton. Moreover, we show a way how to construct the inverse cellular automaton using the method of feasible interpolation from [20]. We also solve two problems regarding complexity of cellular automata formulated by Durand [12] (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Guidelines for dynamics‐based parameterization of one‐dimensional cellular automata rule spaces

As paradigmatic complex systems, various studies have been done in the context of one‐dimensional cellular automata (CA) on the definition of parameters directly obtained from their transition rule, aiming at the help they might provide to forecasting CA dynamic behavior. Out of the analysis of the most important parameters available for this end, as well as others evaluated by us, a set of guidelines is proposed that should be followed when defining a parameter of that kind. Based upon the guidelines, a critique of those parameters is made, which leads to a set of five that jointly provide a good forecasting set; two of them were drawn from the literature and three are new ones defined according to the guidelines. By using them as a heuristic in the evolutionary search for CA of a predefined computational behavior, good results have been obtained, exemplified herein by the evolutionary search for CA that perform the Synchronization Task. © 2001 John Wiley & Sons, Inc.     

Emergent behavior in two complex cellular automata rule sets

Cellular automata systems often produce complex behavior from simple rule sets. The behaviors and results of two complex combinations of cellular automata rules are analyzed. Both two‐dimensional rule sets add complexities to typical cellular automata systems by attaching attributes and rules to each cell. One of the rule sets produces gliders that reproduce upon collision, whereas the other grows into an intricate shape. Projection and entropy analysis classify the rule sets as complex for the intricate shape, but measurements indicate that the self‐reproducing gliders fall between ordered and complex classification, despite their complex appearance. © 2005 Wiley Periodicals, Inc. Complexity 10: 45–55, 2005     

模糊自动机的强连通性及群自动机

为了更好地研究模糊自动机的结构和性质,采用代数的方法,在传统的模糊有限状态自动机的基础上,通过定义状态集合为代数群的自动机,讨论了这一类自动机的连通性和正则性,这丰富了模糊自动机理论．     

模糊Rabin自动机和模糊Game自动机的等价性

自动机是理论计算机的一个重要的研究内容.模糊Rabin自动机和模糊Game自动机是经典自动机的延续,给出了模糊Rabin自动机和模糊Game自动机的相关定义,讨论各自的内在性质,并得到了二者的等价关系.这进一步丰富了模糊自动机理论.     

A cellular automata model can quickly approximate UDP and TCP network traffic

Brooks and Orr [R.R. Brooks and N. Orr, A model for mobile code using interacting automata. IEEE Trans Mobile Computing 2002, 1(4)] present a model for analysis and simulation of mobile code systems based on cellular automata (CA) abstractions. One flaw with that article was a lack of experimental support showing that CA can model IP networks. This article presents CA models, consistent with those in the work of Brooks and Orr, that model the transport layer of IP networks. We show how these models may be generalized for more complicated network topologies. We provide quantitative results comparing the quality of our CA implementation versus the standard network modeling tool ns‐2. The results from the CA model are qualitatively similar to ns‐2, but the CA simulation runs significantly faster and scales better. © 2004 Wiley Periodicals, Inc. Complexity 9:32–40, 2004     

Reversible cellular automata with memory of delay type

The effect of delay type memory of past states on reversible elementary cellular automata (CA) is examined in this study. It is assessed in simple scenarios, such as elementary CA, but the feasibility of enriching the dynamics with memory in a general reversible CA context is also outlined. © 2014 Wiley Periodicals, Inc. Complexity 20: 49–56, 2014     

Structural and functional growth in self‐reproducing cellular automata

In this article, we analyze the dynamics of change in two‐dimensional self‐reproducers, identifying the processes that drive their evolution. We show that changes in self‐reproducers structure and behavior depend on their genetic memory. This consists of distinct yet interlinked components determining their form and function. In some cases these components degrade gracefully, changing only slightly; in others the changes destroy the original structure and function of the self‐reproducer. We sketch these processes at the genotype and the phenotype level—showing that they follow distinct trajectories within mutation space and quantifying the degree of change produced by different trajectories. We show that changes in structure and behavior depend on the interplay between the genotype and the phenotype. This determines universal structures, from which it is possible to construct a great number of self‐reproducing systems, as we observe in biology. Creative processes of change produce divergent and/or convergent methods for the generation of self‐reproducers. Divergence involves the creation of completely new information convergence involves local change and specialization of the structures concerned. © 2006 Wiley Periodicals, Inc. Complexity 11: 12–29, 2006     

An algorithm for testing permutativeness of cellular automata

An effective procedure for deciding permutativeness of one-directional cellular automata on the one-sided full shift is presented. It is then implemented in C++, and used to test permutativeness of elementary cellular automata (those of radius 3).     

Large deviations for mean field models of probabilistic cellular automata

Probabilistic cellular automata form a very large and general class of stochastic processes. These automata exhibit a wide range of complex behavior and are of interest in a number of fields of study, including mathematical physics, percolation theory, computer science, and neurobiology. Very little has been proved about these models, even in simple cases, so it is common to compare the models to mean field models. It is normally assumed that mean field models are essentially trivial. However, we show here that even the mean field models can exhibit surprising behavior. We prove some rigorous results on mean field models, including the existence of a surrogate for the “energy” in certain non‐reversible models. We also briefly discuss some differences that occur between the mean field and lattice models. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The emergence of dynamical complexity: An exploration using elementary cellular automata

This work concerns the interaction between two classical problems: the forecasting of the dynamical behaviors of elementary cellular automata (ECA) from its intrinsic mathematical laws and the conditions that determine the emergence of complex dynamics. To approach these problems, and inspired by the theory of reversible logical gates, we decompose the ECA laws in a “spectrum” of dyadic Boolean gates. Emergent properties due to interactions are captured generating another spectrum of logical gates. The combined analysis of both spectra shows the existence of characteristic bias in the distribution of Boolean gates for ECA belonging to different dynamical classes. These results suggest the existence of signatures capable to indicate the propensity to develop complex dynamics. Logical gates “exclusive‐or” and “equivalence” are among these signatures of complexity. An important conclusion is that within ECA space, interactions are not capable to generate signatures of complexity in the case these signatures are absent in the intrinsic law of the automaton. © 2004 Wiley Periodicals, Inc. Complexity 9: 33–42, 2004     

A decision procedure for well-formed linear quantum cellular automata

In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since it enables us to define the probability of a configuration in an observation as the squared magnitude of its amplitude. We give an efficient algorithm which decides if a linear quantum cellular automaton is well-formed. The complexity of the algorithm is O(n²) in the algebraic model of computation if the input automaton has continuous neighborhood. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 381–394 (1997)     

A novel image encryption algorithm using chaos and reversible cellular automata

In this paper, a novel image encryption scheme is proposed based on reversible cellular automata (RCA) combining chaos. In this algorithm, an intertwining logistic map with complex behavior and periodic boundary reversible cellular automata are used. We split each pixel of image into units of 4 bits, then adopt pseudorandom key stream generated by the intertwining logistic map to permute these units in confusion stage. And in diffusion stage, two-dimensional reversible cellular automata which are discrete dynamical systems are applied to iterate many rounds to achieve diffusion on bit-level, in which we only consider the higher 4 bits in a pixel because the higher 4 bits carry almost the information of an image. Theoretical analysis and experimental results demonstrate the proposed algorithm achieves a high security level and processes good performance against common attacks like differential attack and statistical attack. This algorithm belongs to the class of symmetric systems.     

Asynchronous cellular automata and pattern classification

This article designs an efficient two‐class pattern classifier utilizing asynchronous cellular automata (ACAs). The two‐state three‐neighborhood one‐dimensional ACAs that converge to fixed points from arbitrary seeds are used here for pattern classification. To design the classifier, (1) we first identify a set of ACAs that always converge to fixed points from any seeds, (2) each ACA should have at least two but not huge number of fixed point attractors, and (3) the convergence time of these ACAs are not to be exponential. To address the second issue, we propose a graph, coined as fixed point graph of an ACA that facilitates in counting the fixed points. We further perform an experimental study to estimate the convergence time of ACAs, and find there are some convergent ACAs which demand exponential convergence time. Finally, we identify there are 73 (out of 256) ACAs which can be effective candidates as pattern classifier. We use each of the candidate ACAs on some standard datasets, and observe the effectiveness of each ACAs as pattern classifier. It is observed that the proposed classifier is very competitive and performs reliably better than many standard existing classifier algorithms. © 2016 Wiley Periodicals, Inc. Complexity 21: 370–386, 2016     

模糊逻辑系统中的演绎定理和HS规则

Cancelled the first axiom L1) or the third axiom L3) of the classical formal logic system we established two kinds of quasi-formal deductive system, LG-Rand LG, respectively. In LG-R we proved that neither the deduction theorem nor the hypothetical syllogism (HS) rule held but a deduction theorem and an HS rule are obtained in a weak sense. We also proved that both the deduction theorem and the hypothetical syllogism(HS) rule hold in LG.     

Joint Consistency of Fuzzy Theories

This paper is a contribution to the development of fuzzy logic in narrow sense with evaluated syntax and connectives interpreted in Łukasiewicz algebra. The main results concern model theory of fuzzy logic (various kinds of submodels, chains of models) and generalization of the Craig‐Robinson's theorem on joint consistency of fuzzy theories as well as Craig's interpolation theorem.     

Lyapunov exponents for one-dimensional cellular automata

Summary In the paper we give a mathematical definition of the left and right Lyapunov exponents for a one-dimensional cellular automaton (CA). We establish an inequality between the Lyapunov exponents and entropies (spatial and temporal).     

Renormalization group approach to 1D cellular automata with large updating neighborhoods

We study self‐similarity in one‐dimensional probabilistic cellular automata (PCA) by applying a real‐space renormalization technique to PCA with increasingly large updating neighborhoods. By studying the flow about the critical point of the renormalization, we may produce estimates of the spatial scaling properties of critical PCA. We find that agreement between our estimates and experimental values are improved by resolving correlations between larger blocks of spins, although this is not sufficient to converge to experimental values. However, applying the technique to PCA with larger neighborhoods, and, therefore, more renormalization parameters, results in further improvement. Our most refined estimate produces a spatial scaling exponent, found at the critical point of the five‐neighbor PCA, of ν = 1.056 which should be compared to the experimental value of ν = 1.097. © 2014 Wiley Periodicals, Inc. Complexity 21: 206–213, 2015     

Bisimulations for fuzzy automata

Bisimulations have been widely used in many areas of computer science to model equivalence between various systems, and to reduce the number of states of these systems, whereas uniform fuzzy relations have recently been introduced as a means to model the fuzzy equivalence between elements of two possible different sets. Here we use the conjunction of these two concepts as a powerful tool in the study of equivalence between fuzzy automata. We prove that a uniform fuzzy relation between fuzzy automata A and B is a forward bisimulation if and only if its kernel and co-kernel are forward bisimulation fuzzy equivalence relations on A and B and there is a special isomorphism between factor fuzzy automata with respect to these fuzzy equivalence relations. As a consequence we get that fuzzy automata A and B are UFB-equivalent, i.e., there is a uniform forward bisimulation between them, if and only if there is a special isomorphism between the factor fuzzy automata of A and B with respect to their greatest forward bisimulation fuzzy equivalence relations. This result reduces the problem of testing UFB-equivalence to the problem of testing isomorphism of fuzzy automata, which is closely related to the well-known graph isomorphism problem. We prove some similar results for backward-forward bisimulations, and we point to fundamental differences. Because of the duality with the studied concepts, backward and forward-backward bisimulations are not considered separately. Finally, we give a comprehensive overview of various concepts on deterministic, nondeterministic, fuzzy, and weighted automata, which are related to bisimulations.     

Quantum calculation of thermal effect in quantum‐dot cellular automata

We present a theoretical study of thermal effect in quantum‐dot cellular automata (QCA). An extended Hubbard‐type model for the Hamiltonian of the QCA arrays, and canonical distribution were used to obtain thermal average of polarization for the QCA cells. A full‐basis quantum method has been used for the calculation of response function for a two‐ and a three‐cell array system. Each cell is composed of four dots located at the corners of the cells. Results show that the nonlinear behavior of the response function functions decay with the temperature as well as with the number of cells in the array. © 2005 Wiley Periodicals, Inc. Complexity 10: 73–78, 2005