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 coding method for a sequent calculus of propositional logic

The paper deals with a coding method for a sequent calculus of the propositional logic. The method is based on the sequent calculus. It allows us to determine if a formula is derivable in the calculus without constructing a derivation tree. The main advantage of the coding method is its compactness in comparison with derivation trees of the sequent calculus. The coding method can be used as a decision procedure for the propositional logic.     

扰动模糊命题逻辑的代数结构及其广义重言式性质

着眼于扰动模糊命题逻辑的代数结构,为研究二维扰动模糊命题逻辑最大子代数I2R及其广义重言式提供了一些代数理论基础,最后研究了子代数间广义重言式的关系.     

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     

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).     

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     

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     

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     

Fuzzy automata and life

Boolean cellular automata may be generalized to fuzzy automata in a consistent manner. Several fuzzy logics are used to create 1‐dimensional automata and also 2‐dimensional automata that generalize the game of life. These generalized automata are investigated and compared to their Boolean counterparts empirically and using rule entropy and repeated input response functions. Fuzzy automata offer new mechanisms for classification of classical automata and can be used for insight into their qualitative behavior. © 2002 Wiley Periodicals, Inc.     

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)     

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     

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     

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     

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.     

Are complex systems hard to evolve?

Evolutionary complexity is measured here by the number of trials/evaluations needed for evolving a logical gate in a nonlinear medium. Behavioral complexity of the gates evolved is characterized in terms of cellular automata behavior. We speculate that hierarchies of behavioral and evolutionary complexities are isomorphic up to some degree, subject to substrate specificity of evolution, and the spectrum of evolution parameters. © 2009 Wiley Periodicals, Inc. Complexity, 2009     

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     

Complex genetic evolution of artificial self‐replicators in cellular automata

It is widely believed that evolutionary dynamics of artificial self‐replicators realized in cellular automata (CA) are limited in diversity and adaptation. Contrary to this view, we show that complex genetic evolution may occur within simple CA. The evolving self‐replicating loops (“evoloops”) we investigate exhibit significant diversity in macro‐scale morphologies and mutational biases, undergoing nontrivial genetic adaptation by maximizing colony density and enhancing sustainability against other species. Nonmutable subsequences enable genetic operations that alter fitness differentials and promote long‐term evolutionary exploration. These results demonstrate a unique example of genetic evolution hierarchically emerging from local interactions between elements much smaller than individual replicators. © 2004 Wiley Periodicals, Inc. Complexity 10: 33–39, 2004     

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.     

Non-commutative Łukasiewicz propositional logic

The non-commutative counterpart of the well-known Łukasiewicz propositional logic is developed, in strong connection with the algebraic theory of psMV-algebras. An extension by a new unary logical connective is also considered and a stronger completeness result is proved for this system.     

On the correspondence between arithmetic theories and propositional proof systems – a survey

The purpose of this paper is to survey the correspondence between bounded arithmetic and propositional proof systems. In addition, it also contains some new results which have appeared as an extended abstract in the proceedings of the conference TAMC 2008 [11]. Bounded arithmetic is closely related to propositional proof systems; this relation has found many fruitful applications. The aim of this paper is to explain and develop the general correspondence between propositional proof systems and arithmetic theories, as introduced by Krají?ek and Pudlák [46]. Instead of focusing on the relation between particular proof systems and theories, we favour a general axiomatic approach to this correspondence. In the course of the development we particularly highlight the role played by logical closure properties of propositional proof systems, thereby obtaining a characterization of extensions of EF in terms of a simple combination of these closure properties (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)