Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIntrinsic Simulations between Stochastic Cellular Automata
139
0
0.0
(
0
)
Added by
EPTCS
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Authors
Pablo Arrighi
Ask ChatGPT about the research
No Arabic abstract
The paper proposes a simple formalism for dealing with deterministic, non-deterministic and stochastic cellular automata in a unifying and composable manner. Armed with this formalism, we extend the notion of intrinsic simulation between deterministic cellular automata, to the non-deterministic and stochastic settings. We then provide explicit tools to prove or disprove the existence of such a simulation between two stochastic cellular automata, even though the intrinsic simulation relation is shown to be undecidable in dimension two and higher. The key result behind this is the caracterization of equality of stochastic global maps by the existence of a coupling between the random sources. We then prove that there is a universal non-deterministic cellular automaton, but no universal stochastic cellular automaton. Yet we provide stochastic cellular automata achieving optimal partial universality.
rate research
Read More
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.
Gauge-invariance is a fundamental concept in Physics---known to provide mathematical justification for the fundamental forces. In this paper, we provide discrete counterparts to the main gauge theoretical concepts directly in terms of Cellular Automata. More precisely, the notions of gauge-invariance and gauge-equivalence in Cellular Automata are formalized. A step-by-step gauging procedure to enforce this symmetry upon a given Cellular Automaton is developed, and three examples of gauge-invariant Cellular Automata are examined.
This paper is the second part of a series of two papers dealing with bulking: a way to define quasi-order on cellular automata by comparing space-time diagrams up to rescaling. In the present paper, we introduce three notions of simulation between cellular automata and study the quasi-order structures induced by these simulation relations on the whole set of cellular automata. Various aspects of these quasi-orders are considered (induced equivalence relations, maximum elements, induced orders, etc) providing several formal tools allowing to classify cellular automata.
Gauge-invariance is a mathematical concept that has profound implications in Physics---as it provides the justification of the fundamental interactions. It was recently adapted to the Cellular Automaton (CA) framework, in a restricted case. In this paper, this treatment is generalized to non-abelian gauge-invariance, including the notions of gauge-equivalent theories and gauge-invariants of configurations
We present an underapproximation for context-free languages by filtering out runs of the underlying pushdown automaton depending on how the stack height evolves over time. In particular, we assign to each run a number quantifying the oscillating behavior of the stack along the run. We study languages accepted by pushdown automata restricted to k-oscillating runs. We relate oscillation on pushdown automata with a counterpart restriction on context-free grammars. We also provide a way to filter all but the k-oscillating runs from a given PDA by annotating stack symbols with information about the oscillation. Finally, we study closure properties of the defined class of languages and the complexity of the k-emptiness problem asking, given a pushdown automaton P and k >= 0, whether P has a k-oscillating run. We show that, when k is not part of the input, the k-emptiness problem is NLOGSPACE-complete.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
