FORMENTI , Enrico

Cellular automata are a well-known discrete model for complex systems characterized by local interactions. Indeed, these local interactions cause the emergence of a global complex behavior. Cellular automata essentially consist in an infinite number of identical finite automata arranged on regular grid (ℤ in this talk). Each automaton updates...

This volume contains the proceedings of the 18th International workshop AUTOMATA and the 3rd international symposium JAC. AUTOMATA workshop series aims at gathering researchers from all over the world working in fundamental aspects of cellular automata and related discrete complex systems. Topics cover (although they are not limited to):...

The paper after briefly surveying main asynchronous models in cellular automata will report recent developments in the study of m-ACA, a new general framework for studying asynchrony in cellular spaces.

National audience

In this paper we study the complexity of the decision problems about generic properties on the dynamics of finite discrete dynamical systems (fDDS). Properties are grouped into two main classes : local and global. Local properties are at most in , while global ones are at most in PSPACE. We also investigate universality (w.r.t. simulation) and...

International audience

International audience

International audience

A subshift attractor is a two-sided subshift which is an attractor of a cellular automaton. We prove that each subshift attractor is chain-mixing, contains a configuration which is both F-periodic and $\sigma$-periodic and the complement of its language is recursively enumerable. We prove that a subshift of finite type is an attractor of a...

International audience

International audience

In this paper we study some decidable properties of twodimensional cellular automata (2D CA). The notion of closingness is generalized to the 2D case and it is linked to permutivity and openness. The major contributions of this work are two deep constructions which have been fundamental in order to prove our new results and we strongly believe...

The class of 2-polyominoes contains all polyominoes P such that for any integer i, the first i columns of P consist of at most 2 polyominoes. We provide a decomposition that allows us to exploit suitable discrete dynamical systems to define an algorithm for generating all 2-polyominoes of area n in constant amortized time and space O(n).

International audience

International audience

We construct an algorithm which finds the maximal attractors (limit sets) of certain cellular automata whose maximal attractor is a sofic subshift. The algorithm first finds signal subshifts of a given automaton, constructs their join, and finally forward images of this join. When this procedure stops, the algorithm tests whether a special...

International audience

International audience

International audience

This special issue contains four papers presented during theworkshop, ''18th International Workshop on CellularAutomata and Discrete Complex Systems'' (Automata2012), held in La Marana, Corsica island (France) in theperiod September 19–21th, 2012.The aim of this workshop is to establish and maintain apermanent, international, multidisciplinary...

We prove fixed points results for sandpiles starting with arbitrary initial conditions. We give an effective algorithm for computing such fixed points, and we refine it in the particular case of SPM.

The paper deals with recent developments about non-uniform cellular automata. After reviewing known results about structural stability we complete them by showing that also sensitivity to initial conditions is not structurally stable. The second part of the paper reports the complexity results about the main dy-namical properties. Some proofs...

Extremal combinatorics is the study of the size that a collection of objects must have in order to certainly satisfy a given property. Reaction systems are a recent formalism for computation inspired by chemical reactions. This work is a first contribution to the study of the behavior of large reaction systems by means of extremal...

Extremal combinatorics is the study of the size that a certain collection of objects must have in order to certainly satisfy a property. Reaction systems are a recent formalism for computation inspired by chemical reactions. This work is a first contribution to the study of the behaviour of large reaction systems by means of extremal...