Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Complexity of Asynchronous Freezing Cellular Automata
118
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper we study the family of freezing cellular automata (FCA) in the context of asynchronous updating schemes. A cellular automaton is called freezing if there exists an order of its states, and the transitions are only allowed to go from a lower to a higher state. A cellular automaton is asynchronous if at each time-step only one cell is updated. Given configuration, we say that a cell is unstable if there exists a sequential updating scheme that changes its state. In this context, we define the problem AsyncUnstability, which consists in deciding if a cell is unstable or not. In general AsyncUnstability is in NP, and we study in which cases we can solve the problem by a more efficient algorithm. We begin showing that AsyncUnstability is in NL for any one-dimensional FCA. Then we focus on the family of life-like freezing CA (LFCA), which is a family of two-dimensional two-state FCA that generalize the freezing version of the game of life, known as life without death. We study the complexity of AsyncUnstability for all LFCA in the triangular and square grids, showing that almost all of them can be solved in NC, except for one rule for which the problem is NP-complete.
rate research
Read More
Cellular Automata have been used since their introduction as a discrete tool of modelization. In many of the physical processes one may modelize thus (such as bootstrap percolation, forest fire or epidemic propagation models, life without death, etc), each local change is irreversible. The class of freezing Cellular Automata (FCA) captures this feature. In a freezing cellular automaton the states are ordered and the cells can only decrease their state according to this freezing-order. We investigate the dynamics of such systems through the questions of simulation and universality in this class: is there a Freezing Cellular Automaton (FCA) that is able to simulate any Freezing Cellular Automata, i.e. an intrinsically universal FCA? We show that the answer to that question is sensitive to both the number of changes cells are allowed to make, and geometric features of the space. In dimension 1, there is no universal FCA. In dimension 2, if either the number of changes is at least 2, or the neighborhood is Moore, then there are universal FCA. On the other hand, there is no universal FCA with one change and Von Neumann neighborhood. We also show that monotonicity of the local rule with respect to the freezing-order (a common feature of bootstrap percolation) is also an obstacle to universality.
A novel, information-based classification of elementary cellular automata is proposed that circumvents the problems associated with isolating whether complexity is in fact intrinsic to a dynamical rule, or if it arises merely as a product of a complex initial state. Transfer entropy variations processed by the system split the 256 elementary rules into three information classes, based on sensitivity to initial conditions. These classes form a hierarchy such that coarse-graining transitions observed among elementary cellular automata rules predominately occur within each information- based class, or much more rarely, down the hierarchy.
In this paper we study the family of two-state Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only on the sum of its active neighbors. We classify all the Cellular Automata in the class of TFCA, grouping them in five different classes: the Trivial rules, Turing Universal rules,Algebraic rules, Topological rules and Fractal Growing rules. At the same time, we study in this family the Stability problem, consisting in deciding whether an inactive cell becomes active, given an initial configuration.We exploit the properties of the automata in each group to show that: - For Algebraic and Topological Rules the Stability problem is in $text{NC}$. - For Turing Universal rules the Stability problem is $text{P}$-Complete.
121 -
Demosthenes Ellinas
, Elena P. Papadopoulou
, Yiannis G. Saridakisn (Department of Sciences
2000
A method of quantization of classical soliton cellular automata (QSCA) is put forward that provides a description of their time evolution operator by means of quantum circuits that involve quantum gates from which the associated Hamiltonian describing a quantum chain model is constructed. The intrinsic parallelism of QSCA, a phenomenon first known from quantum computers, is also emphasized.
A cellular automata (CA) configuration is constructed that exhibits emergent failover. The configuration is based on standard Game of Life rules. Gliders and glider-guns form the core messaging structure in the configuration. The blinker is represented as the basic computational unit, and it is shown how it can be recreated in case of a failure. Stateless failover using primary-backup mechanism is demonstrated. The details of the CA components used in the configuration and its working are described, and a simulation of the complete configuration is also presented.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
