Wyniki wyszukiwania - BazTech

1

Periodic Orbits and Dynamical Complexity in Cellular Automata

Dennunzio A., Di Lena P., Formenti E., Margara L.

Fundamenta Informaticae

|

2013

|

Vol. 126, nr 2-3

183--199

EN

We investigate the relationships between dynamical complexity and the set of periodic configurations of surjective Cellular Automata. We focus on the set of strictly temporally periodic configurations, i.e., the set of those configurations which are temporally but not spatially periodic for a given surjective automaton. The cardinality of this set turns out to be inversely related to the dynamical complexity of the cellular automaton. In particular, we show that for surjective Cellular Automata, the set of strictly temporally periodic configurations has strictly positive measure if and only if the cellular automaton is equicontinuous. Furthermore, we show that the set of strictly temporally periodic configurations is dense for almost equicontinuous surjective cellular automata, while it is empty for the positively expansive ones. In the class of additive cellular automata, the set of strictly temporally periodic points can be either dense or empty. The latter happens if and only if the cellular automaton is topologically transitive. This is not true for general transitive Cellular Automata, where the set of of strictly temporally periodic points can be non-empty and non-dense.

2

Computing Issues of Asynchronous CA

Dennunzio A., Formenti E., Manzoni L.

Fundamenta Informaticae

|

2012

|

Vol. 120, nr 2

165-180

EN

This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are “universal”, i.e., allowing a (specific family of) ACA to simulate any Turing machine on any input. We also consider the computational cost of such simulations. Finally, we deal with ACA equipped with peculiar updating sequences, namely those generated by random walks.

3

Computational Complexity of Avalanches in the Kadanoff Sandpile Model

Formenti E., Goles E., Martin B.

Fundamenta Informaticae

|

2012

|

Vol. 115, nr 1

107-124

EN

This paper investigates the avalanche problem AP for the Kadanoff sandpile model (KSPM). We prove that (a slight restriction of) AP is in NC1 in dimension one, leaving the general case open. Moreover, we prove that AP is P-complete in dimension two. The proof of this latter result is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with an initial sand distribution in KSPM. These results are also related to the known prediction problem for sandpiles which is in NC1 for one-dimensional sandpiles and P-complete for dimension 3 or higher. The computational complexity of the prediction problem remains open for the Bak’s model of two-dimensional sandpiles.

4

Advances in Symmetric Sandpiles

Formenti E., Masson B., Pisokas T.

Fundamenta Informaticae

|

2007

|

Vol. 76, nr 1-2

91-112

EN

A symmetric version of the well-known SPM model for sandpiles is introduced. We prove that the new model has fixed-point dynamics. Although there might be several fixed points, a precise description of the fixed points is given. Moreover, we provide a simple closed formula for counting the number of fixed points originated by initial conditions made of a single column of grains. Bounds for the transient length are also given.