Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Symmetry versus Asynchronism: at the Edge of Universality in Automata Networks
84
0
0.0
(
0
)
Added by
Guillaume Theyssier
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Martin Rios Wilson
Ask ChatGPT about the research
No Arabic abstract
An automata network (AN) is a finite graph where each node holds a state from a finite alphabet and is equipped with a local map defining the evolution of the state of the node depending on its neighbors. The global dynamics of the network is then induced by an update scheme describing which nodes are updated at each time step. We study how update schemes can compensate the limitations coming from symmetric local interactions. Our approach is based on intrinsic simulations and universality and we study both dynamical and computational complexity. By considering several families of concrete symmetric AN under several different update schemes, we explore the edge of universality in this two-dimensional landscape. On the way, we develop a proof technique based on an operation of glueing of networks, which allows to produce complex orbits in large networks from compatible pseudo-orbits in small networks.
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.
145 -
Eric Goles (Unconventional Computing Laboratory
, University of then West of England
, Bristol
2021
We consider the problem of studying the simulation capabilities of the dynamics of arbitrary networks of finite states machines. In these models, each node of the network takes two states 0 (passive) and 1 (active). The states of the nodes are updated in parallel following a local totalistic rule, i.e., depending only on the sum of active states. Four families of totalistic rules are considered: linear or matrix defined rules (a node takes state 1 if each of its neighbours is in state 1), threshold rules (a node takes state 1 if the sum of its neighbours exceed a threshold), isolated rules (a node takes state 1 if the sum of its neighbours equals to some single number) and interval rule (a node takes state 1 if the sum of its neighbours belong to some discrete interval). We focus in studying the simulation capabilities of the dynamics of each of the latter classes. In particular, we show that totalistic automata networks governed by matrix defined rules can only implement constant functions and other matrix defined functions. In addition, we show that t by threshold rules can generate any monotone Boolean functions. Finally, we show that networks driven by isolated and the interval rules exhibit a very rich spectrum of boolean functions as they can, in fact, implement any arbitrary Boolean functions. We complement this results by studying experimentally the set of different Boolean functions generated by totalistic rules on random graphs.
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.
Cellular Automaton (CA) and an Integral Value Transformation (IVT) are two well established mathematical models which evolve in discrete time steps. Theoretically, studies on CA suggest that CA is capable of producing a great variety of evolution patterns. However computation of non-linear CA or higher dimensional CA maybe complex, whereas IVTs can be manipulated easily. The main purpose of this paper is to study the link between a transition function of a one-dimensional CA and IVTs. Mathematically, we have also established the algebraic structures of a set of transition functions of a one-dimensional CA as well as that of a set of IVTs using binary operations. Also DNA sequence evolution has been modelled using IVTs.
This paper considers the length of resolution proofs when using Krishnamurthys classic symmetry rules. We show that inconsistent linear equation systems of bounded width over a fixed finite field $mathbb{F}_p$ with $p$ a prime have, in their standard encoding as CNFs, polynomial length resolutions when using the local symmetry rule (SRC-II). As a consequence it follows that the multipede instances for the graph isomorphism problem encoded as CNF formula have polynomial length resolution proofs. This contrasts exponential lower bounds for individualization-refinement algorithms on these graphs. For the Cai-Furer-Immerman graphs, for which Toran showed exponential lower bounds for resolution proofs (SAT 2013), we also show that already the global symmetry rule (SRC-I) suffices to allow for polynomial length proofs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
