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

From One-dimensional to Two-dimensional Cellular Automata

Dennunzio A.

Fundamenta Informaticae

|

2012

|

Vol. 115, nr 1

87-105

EN

We enlighten the differences between one-dimensional and two-dimensional cellular automata by considering both the dynamical and decidability aspects. We also show a canonical representation theorem for the slicing constructions, a tool allowing to give the 2D version of important 1D CA notions as closing and positive expansivity and lift 1D results to the 2D settings.

3

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.

4

A Predator-Prey Cellular Automaton with Parasitic Interactions and Environmental Effects

Farina F., Dennunzio A.

Fundamenta Informaticae

|

2008

|

Vol. 83, nr 4

337-353

EN

We propose a lattice model to describe a predator-prey system where two species with significantly different size are considered. The biological analogy we refer to is the predatory interaction between bacteria and viruses. We assume simple environmental effects altering the dynamics. Preys (bacteria) procreate by mitosis and they do not move. They may die because of natural causes or under the predation. The predation is the consequence of a diffusive phenomenon by the predators (viruses). Predators grow in number by infection and by prey self-immunity diseases, and they die by starvation.

5

Chaotic Subshifts and Related Languages Applications to one-dimensional Cellular Automata

Cattaneo G., Dennunzio A., Margara L.

Fundamenta Informaticae

|

2002

|

Vol. 52, nr 1-3

39-80

EN

Subshift behaviors of one-dimensional (1D) bi-infinite Cellular Automata are studied. In particular the conditions under which subshifts generated by CA 1D dynamical systems exhibit some components of the chaotic behavior (in particular transitivity, topological mixing and strong transitivity) are investigated. A complete classification of all elementary (Boolean radius one) CA with respect to subshifts is given.