Keynotes

Nazim Fates, Inria Nancy

Self-stablisation in cellular systems

Remaining constant in a noisy environment is a difficult task, which is is achieved "by design" -- if we may say so -- by living organisms. Cellular automata were invented to study self-reproduction ; since then, this computing model have been the source of many problems regarding self-organisation, self-repair, self-diagnosis, and other “self-star” properties, which are found in living organisms. We propose to examine the problem of self-stabilisation as initially defined by Dijkstra: given a set of legal sets, how can a cellular automaton return to this set if it undergoes an external perturbation? More generally we would like to ask why the reproduction of robust mechanisms found in Nature is so tedious. Would it be that there is no "Newton of the blade of grass”? We do not aim to fully answer this question but simply to illustrate it with some selected deterministic and probabilistic cellular automata.

Georgios Sirakoulis, Democritus University of Thrace

Improving the Capabilities of Cellular Automata Modeling through Hardware Implementation

Cellular Automata (CAs) are a highly effective computational model well known for their ability to accurately model, simulate and replicate a wide range of complicated physical systems and processes. CAs include two notable and quite interesting characteristics, namely inherent parallelism, and locality, which render them exceptionally well-suited for the realization of appropriate computer systems. These traits also help alleviate the persistent issue of data transmission between memory and processor, commonly referred to as the von Neumann bottleneck named as one of the most ongoing complex issues in computer science and hardware. This talk will explore the use of CAs as a powerful unique computational architecture and will discuss their potential application in several kinds of conventional and unconventional computing. Furthermore, advanced unconventional computational materials, tools, methods and architectures coupled with CAs, such as cellular automata with memristors, oscillating circuits, quantum cellular automata (CA), and graphene-based CA will be introduced. These novel hardware tools and techniques have the potential to enhance the capabilities of CAs, providing additional levels of efficiency and functionality for the advanced modeling of physical and chemical systems. The talk will conclude with the presentation of the advantages of the dedicated hardware implementations of CAs while aiming to improve the efficiency of CA models in numerous fields including physics, chemistry, ecology, geology, biology, and computer science.

Alberto Dennunzio, University of Milano Bicocca

Theory of Cellular Automata: from the Past and Present to Some Path towards the Future

Cellular Automata (CA) are discrete formal models introduced by J. von Neumann and S. Ulam in the late 1940s that at the same time define paradigmatic Discrete Time Dynamical Systems (DTDS) (due to the huge variety of distinct dynamical behaviors of general DTDS they exhibit) and describe Complex Systems, i.e., multitudes of elementary components which cooperate and produces emerging complex behaviors. For these reasons CA are used with success in many and different scientific fields for modelling phenomena and processes with complicated behaviors.

As a matter of fact, a CA is a pair (SL, F), where S is a set called the set of states, or alphabet, of the CA, L is a d-dimensional regular lattice of elements (usually, vectors of Zd, and in particular L = Zd), called cells, each of them associated with a state of S, and F : SL → SL is a function, called global transition map of the CA, or CA global rule, defined according to a local rule f : S|N| → S that updates the state of each cell on the basis of the states of a finite set N , called neighborhood, of neighboring cells. The lattice L can be also viewed as the vertex set of a regular labelled graph. The states of all the cells are updated synchronously at each discrete time step. In this way, the global transition map F describes the overall updating of the states of all the cells, i.e., the updating of a certain element of SL, called configuration, and hence the sequence {Ft(c)}t∈N is nothing but the dynamical evolution, or orbit, of the CA starting from the initial configuration c ∈ SL. Some CA variants were introduced, namely, as non-uniform CA and asynchronous CA, obtained by relaxing the uniformity and synchrony in CA definition, i.e., in such a way that cells can update according to distinct local rules and in an asynchronous way, respectively. Probabilistic CA, i.e., CA defined by a probabilistic local rule also receive a significant attention. An infinite lattice L is often considered in order that CA and variants are able to capture some important features of the real-world.

A deep mathematical theory of CA was started in the late 1960s by the mathematician Gustav A. Hedlund who studied them in the context of symbolic dynamics. Many researches followed about the theoretic set and dynamical properties of DTDS in the context of CA (over an infinite lattice): injectivity, surjectivity, openness, equicontinuity, almost equicontinuity, sensitivity to the initial conditions, positive expansivity, topological transitivity, topological mixing, topological chaos, topological entropy. The study of the CA dynamics allowed understanding their main features as DTDS: reachability, reversibility, stability, instability, chaos, periodic behaviors, etc. Such features are nothing but typical behaviors seen in real-world phenomena and artificial processes used in applications. Therefore, when CA are used for modelling such phenomena and processes, they must exhibit the corresponding dynamical properties. Unfortunately, almost all the dynamical properties of DTDS raised by CA turned out to be undecidable. This is an obstacle when one wants to model a certain phenomenon or an artificial process by a CA being sure that the latter is appropriate in the considered case of study. So, researches also focused and are still focusing on the identification and the investigation of classes of CA automata which are expressive enough (i.e, able to exhibit the complex behaviours of general CA) and, at the same time, allow one to establish a given dynamical behavior (i.e, in those classes the dynamical properties become decidable). Linear CA and Additive CA are just paradigmatic examples of such classes. The current investigations concern the decidability of the dynamical properties and the efficiency issue of the decision algorithms, the latter being largely unexplored probably due to the fact that, as far as infinite lattices are concerned, the focus in CA research has been in (un)decidability.

As to CA and variants with a finite lattice L, they are used too in applications for modelling several phenomena, including the diffusive ones. From a theoretical point of view, due to the finiteness of L, a crucial focus is on problems regarding the finite sets of fixed/periodic points, attractors, transients, the reachability and synchronization issues of the finite DTDS defined by such models. Clearly, when the set of state is finite too, the finiteness implies that all the problems involving these aspects are decidable. However, the computational complexity land- scape of solving such problems is currently largely unexplored. There is then a lack of results that obstacle a more proper and most effective use of finite CA and variants in applications. Indeed, as an example, to face real sce- narios one has to master every aspect around the global steady or cyclic global state of that phenomenon. This is reflected on the model used for describing the phenomenon in the need of being able to answer questions about the dynamics of the induced DTDS in an efficient way. So, researchers are still considering relevant problems over the dynamics of the DTDS defined by finite CA and variants along with finding out efficient algorithms that solve them: computing the number of fixed/periodic points and attractors, computing the lengths of cycles and transients (maximum, minimum length), establishing some property on all these, stating some reachability forms and deciding it, etc.

Some meaningful future research directions in CA theory are:

• Higher Dimensional Scenario. Driven by applications that inherently also involve two and higher dimensional spaces (for instance, think of diffusive phenomena in real two/three-dimensional spaces or cryptographic protocols regarding two-dimensional data), DTDS raised by CA defined over a two and higher dimensional lattice should be considered in depth. Therefore, results are required for both one-dimensional and multidi- mensional CA. We stress that, due to its high complexity, the CA multidimensional scenario potentially offers security advantages over the one-dimensional setup, as for instance in the case of cryptographic protocols, where it deserves to be investigated also for dealing with one-dimensional data.

• ControlTheoryinCA.Thecomplexityofrealsystemsrequiresthataspectsfromcontroltheoryareconsidered too when studying formal models for complex systems. The problems of observability and controllability are among the main issues in the context of control theory. First important works dealing with observability and controllability in CA settings have been recently presented. A comprehensive CA control theory integrating that of the dynamical properties is expected so that CA can be used to model real complex systems even more accurately.

• Data-driven Synthesis of CA. There is no general method that, given the description of a real complex sy- stem (which reasonably lends itself to be modelled by CA) in terms of data regarding its real dynamics, automatically provides the CA local rules, or a set of local rules, able to suitably model it. Theoretical results regarding parametrized families of CA to be learned are needed to develop one or a collection of such methods that would have a significant impact on the general modelling problem.

The current investigations on CA theory are carried out worldwide and through international collaborations. However, at our best knowledge, there are very few projects funded on an international scale. The themes illustrated in the above mentioned research directions could be the subjects of CA theory project proposals on an international scale. I believe that, due to their relevance, these subject would increase themselves the chance of proposals being selected for funding.