Entropy of multidimensional cellular automata

Since the topological entropy of a vast class of two-dimensional cellular automata (CA) is infinite, of interest is the possibility to renormalize it so that to obtain a positive finite value. We find the asymptotics of the information function of a multidimensional CA and, accordingly, introduce the renormalized topological entropy as a coefficient of this asymptotics. We describe some properties of the introduced quantity, in particular, its positivity for CA of the type of “The Game of Life.” Also, we give an example of an explicit evaluation of this parameter for a particular cellular automaton.     

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.     

Selfing dynamics in the rule space of additive cellular automata

A unique aspect of additive cellular automata (CA) rules is that the state space on which these rules operate is also the representation space for the rules. Thus, a rule can operate on itself to produce a new rule that is not just its square. This operation will be called selfing, in analogy to reproduction by selfing in Mendelian genetics. This paper explains the properties of the selfing operation on one-dimensional binary-valued additive CA. Results characterizing the selfing transition diagram are derived and some suggestions as to possible applications are presented. The most transparent expression of results is given by representing both rules and states in terms of roots of unity, and this formalism is briefly developed in the initial section.     

Monitoring the Formation of Kernel-Based Topographic Maps in a Hybrid SOM-kMER Model

A new lattice disentangling monitoring algorithm for a hybrid self-organizing map-kernel-based maximum entropy learning rule (SOM-kMER) model is proposed. It aims to overcome topological defects owing to a rapid decrease of the neighborhood range over the finite running time in topographic map formation. The empirical results demonstrate that the proposed approach is able to accelerate the formation of a topographic map and, at the same time, to simplify the monitoring procedure.     

Neighborhood detection and rule selection from cellular automatapatterns

Using genetic algorithms (GAs) to search for cellular automation (CA) rules from spatio-temporal patterns produced in CA evolution is usually complicated and time-consuming when both, the neighborhood structure and the local rule are searched simultaneously. The complexity of this problem motivates the development of a new search which separates the neighborhood detection from the GA search. In the paper, the neighborhood is determined by independently selecting terms from a large term set on the basis of the contribution each term makes to the next state of the cell to be updated. The GA search is then started with a considerably smaller set of candidate rules pre-defined by the detected neighhorhood. This approach is tested over a large set of one-dimensional (1-D) and two-dimensional (2-D) CA rules. Simulation results illustrate the efficiency of the new algorithm     

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.     

Piecewise Polynomial Sequences over the Galois Ring

Problems of Information Transmission - We describe the construction of a piecewise polynomial generator over a Galois ring and prove a transitivity criterion for it. We give an estimate for the...     

A construction of five-state real-time Fibonacci sequence generator

A cellular automaton (\(\mathrm {CA}\)) is a well-studied non-linear computational model of complex systems in which an infinite one-dimensional array of finite state machines (cells) updates itself in a synchronous manner according to a uniform local rule. A sequence generation problem on the \(\mathrm {CA}\) model has been studied for a long time and a lot of generation algorithms has been proposed for a variety of non-regular sequences such as \(\{2^n \,|\,n = 1, 2, 3,\ldots \}\), prime, and Fibonacci sequences, etc. In this paper, we propose a five-state real-time generator for Fibonacci sequence and give a formal proof of the correctness of the generator. The proposed five-state Fibonacci sequence generator is optimum in generation steps, and it is realized on a smallest, known at present finite state automaton in the number of states.     

Quantum correlation and quantum phase transition in the one-dimensional extended Ising model

Quantum phase transitions can be understood in terms of Landau’s symmetry-breaking theory. Following the discovery of the quantum Hall effect, a new kind of quantum phase can be classified according to topological rather than local order parameters. Both phases coexist for a class of exactly solvable quantum Ising models, for which the ground state energy density corresponds to a loop in a two-dimensional auxiliary space. Motivated by this we study quantum correlations, measured by entanglement and quantum discord, and critical behavior seen in the one-dimensional extended Ising model with short-range interaction. We show that the quantum discord exhibits distinctive behaviors when the system experiences different topological quantum phases denoted by different topological numbers. Quantum discords capability to detect a topological quantum phase transition is more reliable than that of entanglement at both zero and finite temperatures. In addition, by analyzing the divergent behaviors of quantum discord at the critical points, we find that the quantum phase transitions driven by different parameters of the model can also display distinctive critical behaviors, which provides a scheme to detect the topological quantum phase transition in practice.     

Stochastic Cellular Automata Solutions to the Density Classification Problem

In the density classification problem, a binary cellular automaton (CA) should decide whether an initial configuration contains more 0s or more 1s. The answer is given when all cells of the CA agree on a given state. This problem is known for having no exact solution in the case of binary deterministic one-dimensional CA. We investigate how randomness in CA may help us solve the problem. We analyse the behaviour of stochastic CA rules that perform the density classification task. We show that describing stochastic rules as a “blend” of deterministic rules allows us to derive quantitative results on the classification time and the classification time of previously studied rules. We introduce a new rule whose effect is to spread defects and to wash them out. This stochastic rule solves the problem with an arbitrary precision, that is, its quality of classification can be made arbitrarily high, though at the price of an increase of the convergence time. We experimentally demonstrate that this rule exhibits good scaling properties and that it attains qualities of classification never reached so far.     

A cryptographic and coding-theoretic perspective on the global rules of cellular automata

Cellular Automata (CA) have widely been studied to design cryptographic primitives such as stream ciphers and pseudorandom number generators, focusing in particular on the properties of the underlying local rules. On the other hand, there have been comparatively fewer works concerning the applications of CA to the design of S-boxes and block ciphers, a task that calls for a study of CA global rules in terms of vectorial boolean functions. The aim of this paper is to analyze some of the most basic cryptographic criteria of the global rules of CA. We start by observing that the algebraic degree of a CA global rule equals the degree of its local rule. Then, we characterize the Walsh spectrum of CA induced by permutive local rules, from which we derive a formula for the nonlinearity of such CA. Additionally, we prove that the 1-resiliency property of bipermutive local rules transfers to the corresponding global rules. This result leads us to consider CA global rules from a coding-theoretic point of view: in particular, we show that linear CA are equivalent to linear cyclic codes, observing that the syndrome computation process corresponds to the application of the CA global rule, while the error-correction capability of the code is related to the resiliency order of the global rule.     

Entropy of a stationary process and entropy of a shift transformation in its sample space

We construct a class of non-Markov discrete-time stationary random processes with countably many states for which the entropy of the one-dimensional distribution is infinite, while the conditional entropy of the “present” given the “past” is finite and coincides with the metric entropy of a shift transformation in the sample space. Previously, such situation was observed in the case of Markov processes only.     

On the hierarchy of conservation laws in a cellular automaton

Conservation laws in cellular automata (CA) are studied as an abstraction of the conservation laws observed in nature. In addition to the usual real-valued conservation laws we also consider more general group-valued and semigroup-valued conservation laws. The (algebraic) conservation laws in a CA form a hierarchy, based on the range of the interactions they take into account. The conservation laws with smaller interaction ranges are the homomorphic images of those with larger interaction ranges, and for each specific range there is a most general law that incorporates all those with that range. For one-dimensional CA, such a most general conservation law has—even in the semigroup-valued case—an effectively constructible finite presentation, while for higher-dimensional CA such effective construction exists only in the group-valued case. It is even undecidable whether a given two-dimensional CA conserves a given semigroup-valued energy assignment. Although the local properties of this hierarchy are tractable in the one-dimensional case, its global properties turn out to be undecidable. In particular, we prove that it is undecidable whether this hierarchy is trivial or unbounded. We point out some interconnections between the structure of this hierarchy and the dynamical properties of the CA. In particular, we show that positively expansive CA do not have non-trivial real-valued conservation laws.     

The Galois lattice as a hierarchical structure for topological relations

This paper presents the construction and the comparison of Galois lattices of topological relations for qualitative spatial representation and reasoning. The lattices rely on a correspondence between computational operations working on quantitative data, on the one hand, and topological relations working on qualitative knowledge units, on the other hand. After introducing the context of the present research work, i.e. the RCC-8 model of topological relations, we present computational operations for checking topological relations on spatial regions. From these operations are derived two sets of computational conditions that can be associated to topological relations through a Galois connection. The associated Galois lattices are presented and compared. Elements on the practical use of the lattices for representing spatial knowledge and for reasoning are also introduced and discussed.     

An Algorithm of Katz and its Application to the Inverse Galois Problem

In this paper we present a new and elementary approach for proving the main results of Katz (1996) using the Jordan–Pochhammer matrices of Takano and Bannai (1976) and Haraoka (1994). We find an explicit version of the middle convolution of Katz (1996) that connects certain tuples of matrices in linear groups. From this, Katz’ existence algorithm for rigid tuples in linear groups can easily be deduced. It can further be shown that the convolution operation on tuples commutes with the braid group action. This yields a new approach in inverse Galois theory for realizing subgroups of linear groups regularly as Galois groups over Q. This approach is then applied to realize numerous series of classical groups regularly as Galois groups over Q. In the Appendix we treat an additive version of the convolution.     

A class of injective compressing maps on linear recurring sequences over a Galois ring

We consider pseudorandom sequences v over a field GF(p ^r ) obtained by mapping ℓ-grams of a linear recurring sequence u over a Galois ring to an arbitrary coordinate set. We study the possibility of uniquely reconstructing u given v. Earlier known results are briefly overviewed.     

Extension of cellular automata via the introduction of an algorithm for the recursive estimation of neighbors

This study focuses on an extended model of standard cellular automaton (CA), which includes an extra index, comprising a radius that defines a perception area for each cell in addition to the radius defined by the CA rule. Such an extension can be realized by introducing a recursive algorithm called the “Recursive Estimation of Neighbors.” The extended CA rules form a sequence ordered by this index, which includes the CA rule as its first term. This extension aims to construct a model that can be used within the CA framework to study the relation between information processing and pattern formation in collective systems. Even though the extension presented here is merely an extrapolation to a CA having a larger rule neighborhood identical to the perception area, the extra radius can be interpreted as an individual attribute of each cell. The novel perspective to CA provided here makes it possible to build heterogeneous CAs, which contain cells having different extra radii. Several pattern formations in the extension of one-dimensional elementary CAs and two-dimensional Life-like CAs are presented. It is expected that the extended model can be applied to various simulations of complex systems and in other fields.     

Conditional Fuzzy Entropy of Maps in Fuzzy Systems

The fuzzy entropy was investigated as an isomorphism invariant in the last decade. The aim of this paper is to define and study a new invariant called conditional fuzzy entropy which is an extension of fuzzy entropy on fuzzy dynamical systems. This new invariant possesses some basic properties, such as isomorphic invariant, power rule, affinity, and generator. The analysis used in the proof of these properties relies on more techniques of ergodic theory and topological dynamics.     

一维加性扩展CA的伪随机序列的生成方法

随机序列在密码学中有广泛的应用,随机序列发生方法已成为密码学的重要研究课题之一。针对扩展元胞自动机中搜索空间过大的问题,构造出一维加性扩展元胞自动机模型。结果表明,该文的发生方法具有较好的性能,为密码学中的随机序列提供了一种新的发生方法。