Discrete Mathematics & Theoretical Computer Science |

In this paper, we significantly improve a previous result by the same author showing the existence of a weakly universal cellular automaton with five states living in the hyperbolic $3D$-space. Here, we get such a cellular automaton with three states only.

Section:
Proceedings

We discuss a very close relation between minimal recurrent configurations of Chip Firing Games and Directed Acyclic Graphs and demonstrate the usefulness of this relation by giving a lower bound for the number of minimal recurrent configurations of the Abelian Sandpile Model as well as a lower bound for the number of firings which are caused by the addition of two recurrent configurations on particular graphs.

Section:
Proceedings

We study how hard is to determine some fundamental properties of dynamics of certain types of network automata. We address the computational complexity of determining how many different possible dynamic evolutions can arise from some structurally very simple, deterministic and sparsely connected network automata. In this as well as our prior, related work, we try to push the limits on the underlying simplicity of two structural aspects of such network automata: (i) the uniform sparseness of their topologies, and (ii) severely restricted local behaviors of the individual agents (that is, the local update rules of the network nodes). In this endeavor, we prove that counting the Fixed Point (FP) configurations and the predecessor and ancestor configurations in two classes of network automata, called Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively), are computationally intractable problems. Moreover, this intractability is shown to hold when each node in such a network is required to update according to (i) a monotone Boolean function, (ii) a symmetric Boolean function, or even (iii) a simple threshold function that is both monotone and symmetric. Furthermore, the hardness of the exact enumeration of FPs and other types of configurations of interest remains to hold even in some severely restricted cases with respect to both the network topology and the diversity (or lack thereof) of individual node's local update rules. Namely, we show that the […]

Section:
Proceedings

We investigate the descriptional complexity of basic operations on real-time one-way cellular automata with an unbounded as well well as a fixed number of cells. The size of the automata is measured by their number of states. Most of the bounds shown are tight in the order of magnitude, that is, the sizes resulting from the effective constructions given are optimal with respect to worst case complexity. Conversely, these bounds also show the maximal savings of size that can be achieved when a given minimal real-time OCA is decomposed into smaller ones with respect to a given operation. From this point of view the natural problem of whether a decomposition can algorithmically be solved is studied. It turns out that all decomposition problems considered are algorithmically unsolvable. Therefore, a very restricted cellular model is studied in the second part of the paper, namely, real-time one-way cellular automata with a fixed number of cells. These devices are known to capture the regular languages and, thus, all the problems being undecidable for general one-way cellular automata become decidable. It is shown that these decision problems are $\textsf{NLOGSPACE}$-complete and thus share the attractive computational complexity of deterministic finite automata. Furthermore, the state complexity of basic operations for these devices is studied and upper and lower bounds are given.

Section:
Proceedings

It is a well-known fact that the spacetime diagrams of some cellular automata have a fractal structure: for instance Pascal's triangle modulo $2$ generates a Sierpinski triangle. Explaining the fractal structure of the spacetime diagrams of cellular automata is a much explored topic, but virtually all of the results revolve around a special class of automata, whose main features include irreversibility, an alphabet with a ring structure and a rule respecting this structure, and a property known as being (weakly) $p$-Fermat. The class of automata that we study in this article fulfills none of these properties. Their cell structure is weaker and they are far from being $p$-Fermat, even weakly. However, they do produce fractal spacetime diagrams, and we will explain why and how. These automata emerge naturally from the field of quantum cellular automata, as they include the classical equivalent of the Clifford quantum cellular automata, which have been studied by the quantum community for several reasons. They are a basic building block of a universal model of quantum computation, and they can be used to generate highly entangled states, which are a primary resource for measurement-based models of quantum computing.

Section:
Proceedings

Expander graphs are useful in the design and analysis of communication networks. Mukhopadhyay et al. introduced a method to generate a family of expander graphs based on nongroup two predecessor single attractor Cellular Automata(CA). In this paper we propose a method to generate a family of expander graphs based on 60/102 Null Boundary CA(NBCA) which is a group CA. The spectral gap generated by our method is maximal. Moreover, the spectral gap is larger than that of Mukhopadhyay et al.

Section:
Proceedings

We present a method of solving of the probabilistic initial value problem for cellular automata (CA) using CA rule 172 as an example. For a disordered initial condition on an infinite lattice, we derive exact expressions for the density of ones at arbitrary time step. In order to do this, we analyze topological structure of preimage trees of finite strings of length 3. Level sets of these trees can be enumerated directly using classical combinatorial methods, yielding expressions for the number of $n$-step preimages of all strings of length 3, and, subsequently, probabilities of occurrence of these strings in a configuration obtained from the initial one after $n$ iterations of rule 172. The density of ones can be expressed in terms of Fibonacci numbers, while expressions for probabilities of other strings involve Lucas numbers. Applicability of this method to other CA rules is briefly discussed.

Section:
Proceedings

Our work is set in the framework of complex dynamical systems and, more precisely, that of Boolean automata networks modeling regulation networks. We study how the choice of an update schedule impacts on the dynamics of such a network. To do this, we explain how studying the dynamics of any network updated with an arbitrary block-sequential update schedule can be reduced to the study of the dynamics of a different network updated in parallel. We give special attention to networks whose underlying structure is a circuit, that is, Boolean automata circuits. These particular and simple networks are known to serve as the "engines'' of the dynamics of arbitrary regulation networks containing them as sub-networks in that they are responsible for their variety of dynamical behaviours. We give both the number of attractors of period $p$, $\forall p\in \mathbb{N}$ and the total number of attractors in the dynamics of Boolean automata circuits updated with any block-sequential update schedule. We also detail the variety of dynamical behaviours that such networks may exhibit according to the update schedule.

Section:
Proceedings

The biggest obstacle to the efficient discovery of conserved energy functions for cellular auotmata is the elimination of the trivial functions from the solution space. Once this is accomplished, the identification of nontrivial conserved functions can be accomplished computationally through appropriate linear algebra. As a means to this end, we introduce a general theory of trivial conserved functions. We consider the existence of nontrivial additive conserved energy functions ("nontrivials") for cellular automata in any number of dimensions, with any size of neighborhood, and with any number of cell states. We give the first known basis set for all trivial conserved functions in the general case, and use this to derive a number of optimizations for reducing time and memory for the discovery of nontrivials. We report that the Game of Life has no nontrivials with energy windows of size 13 or smaller. Other $2D$ automata, however, do have nontrivials. We give the complete list of those functions for binary outer-totalistic automata with energy windows of size 9 or smaller, and discuss patterns we have observed.

Section:
Proceedings