Search

Un Sistema Dinamico finito a tempo Discreto (SDD) è costituito da un insieme finito X, chiamato insieme degli stati, e da una funzione f che associa a uno stato v lo stato f(v). I SDD sono uno modello formale per rappresentare fenomeni che compaiono in Fisica, Matematica, Biologia e, naturalmente, in Informatica. Sebbene la formalizzazione matematica e i risultati ottenuti fino ad oggi siano eleganti e significativi, spesso non sono molto adatti nella pratica a causa del loro elevato costo computazionale. In letteratura è noto che i SDD, dotati di opportune operazioni di somma e prodotto, formano un semianello commutativo. Questa struttura algebrica permette di scrivere equazioni polinomiali in cui i coefficienti e le incognite sono SDD. In particolare, se siamo interessati a una dinamica derivata da dati sperimentali, possiamo scrivere un'equazione con la dinamica come termine destro costante e le ipotesi sulla funzione f (o sulle sue proprietà) in un termine polinomiale a sinistra. La ricerca di soluzioni a questa equazione permette di comprendere meglio il fenomeno e le sue proprietà. Questo approccio è interessante, ma presenta importanti limitazioni dal punto di vista computazionale. La soluzione di un'equazione polinomiale (con diverse variabili) è, in generale, indecidibile e, anche se ci concentriamo sul caso della validazione delle ipotesi, il costo computazionale rimane elevato. L'idea è quindi quella di cercare approssimazioni che diano informazioni rilevanti sulle soluzioni dell'equazione originale. È possibile introdurre tre astrazioni (equazioni più semplici) per identificare: il numero di stati delle variabili, il comportamento asintotico o il comportamento transitorio (ciò che accade prima che il sistema si stabilizzi). Ognuna di esse è costruita da un punto di vista teorico e algoritmico per introdurre un metodo per eseguire la validazione delle ipotesi sui SDD. In questa tesi si dimostra che, attraverso trasformazioni algebriche, è poss, A Finite Discrete-time Dynamical System (DDS) consists of a finite set X, called state space, and a function f, called next-state map (which associates to a state v the state f(v)). DDS are a formal tool for modelling phenomena that appear in Physics, Mathematics, Biology, and, of course, in Computer Science. While the mathematical formalisation and the results that found up to nowadays are elegant and meaningful, often they are not very suitable in practice because of their high computational cost. In the literature, it is known that DDS equipped with appropriate sum and product operations form a commutative semiring. This algebraic structure allows us to write polynomial equations in which the coefficients and unknowns are DDS. In particular, if we are interested in some dynamics derived from experimental data, we can write an equation with this as a constant right-hand term and model assumptions about the function f (or its properties) in a polynomial left-hand term. Finding solutions to this equation allow us to better understand the phenomenon and its properties. This approach is interesting but it has important limitations from a computational point of view. Solving a polynomial equation (with several variables) is, in general, undecidable, and even if we focus on the case of hypothesis validation, the computational cost remains high. The idea is then to look for approximations that give relevant information about the solutions of the original equation. It is possible to introduce three abstractions (simpler equations) to identify: the number of states of the variables, the asymptotic behaviour, or the transient behaviour (what happens before the system stabilises). Each one is built from a theoretical and algorithmic point of view to introduce a method to perform hypothesis validation on DDS. In this thesis, it is shown that through algebraic transformations, it is possible to enumerate the solutions of a polynomial equation with a constant term by enumeratin

Cellular Automata have successfully been applied to the modeling and simulation of pedestrian dynamics. These simulations have often been focused on the evaluation of situations of medium-high density, in which the motivation of pedestrians overcomes natural proxemic tendencies. The COVID-19 outbreak has shown that in certain situations it is instead crucial to focus on situations in which proxemic is amplified by the particular affective state of the individuals involved in the studied scenario. We present the first steps in a research effort aimed at integrating results of quantitative analyses concerning effects of affective states on the perception of mutual distances by pedestrians of different type and the modeling of movement choices in a cellular automata framework.

We continue the study of asynchrony immunity in cellular automata (CA), which can be considered as a generalization of correlation immunity in the case of vectorial Boolean functions. The property could have applications as a countermeasure for side-channel attacks in CA-based cryptographic primitives, such as S-boxes and pseudorandom number generators. We first give some theoretical results on the properties that a CA rule must satisfy in order to meet asynchrony immunity, like central permutivity. Next, we perform an exhaustive search of all asynchrony immune CA rules of neighborhood size up to 5, leveraging on the discovered theoretical properties to greatly reduce the size of the search space., Cyber Security

We study the dynamical behavior of D-dimensional (D >= 1) additive cellular automata where the alphabet is any finite abelian group. This class of discrete time dynamical systems is a generalization of the systems extensively studied by many authors among which one may list [Masanobu Ito et al., 1983; Giovanni Manzini and Luciano Margara, 1999; Giovanni Manzini and Luciano Margara, 1999; Jarkko Kari, 2000; Gianpiero Cattaneo et al., 2000; Gianpiero Cattaneo et al., 2004]. Our main contribution is the proof that topologically transitive additive cellular automata are ergodic. This result represents a solid bridge between the world of measure theory and that of topology theory and greatly extends previous results obtained in [Gianpiero Cattaneo et al., 2000; Giovanni Manzini and Luciano Margara, 1999] for linear CA over Z_m i.e. additive CA in which the alphabet is the cyclic group Z_m and the local rules are linear combinations with coefficients in Z_m. In our scenario, the alphabet is any finite abelian group and the global rule is any additive map. This class of CA strictly contains the class of linear CA over Z_m^n, i.e., with the local rule defined by n x n matrices with elements in Z_m which, in turn, strictly contains the class of linear CA over Z_m. In order to further emphasize that finite abelian groups are more expressive than Z_m we prove that, contrary to what happens in Z_m, there exist additive CA over suitable finite abelian groups which are roots (with arbitrarily large indices) of the shift map. As a consequence of our results, we have that, for additive CA, ergodic mixing, weak ergodic mixing, ergodicity, topological mixing, weak topological mixing, topological total transitivity and topological transitivity are all equivalent properties. As a corollary, we have that invertible transitive additive CA are isomorphic to Bernoulli shifts. Finally, we provide a first characterization of strong transitivity for additive CA which we suspect it might be true also for the general case.

We study the dynamical behavior of D-dimensional (D >= 1) additive cellular automata where the alphabet is any finite abelian group. This class of discrete time dynamical systems is a generalization of the systems extensively studied by many authors among which one may list [Masanobu Ito et al., 1983; Giovanni Manzini and Luciano Margara, 1999; Giovanni Manzini and Luciano Margara, 1999; Jarkko Kari, 2000; Gianpiero Cattaneo et al., 2000; Gianpiero Cattaneo et al., 2004]. Our main contribution is the proof that topologically transitive additive cellular automata are ergodic. This result represents a solid bridge between the world of measure theory and that of topology theory and greatly extends previous results obtained in [Gianpiero Cattaneo et al., 2000; Giovanni Manzini and Luciano Margara, 1999] for linear CA over Z_m i.e. additive CA in which the alphabet is the cyclic group Z_m and the local rules are linear combinations with coefficients in Z_m. In our scenario, the alphabet is any finite abelian group and the global rule is any additive map. This class of CA strictly contains the class of linear CA over Z_m^n, i.e. , with the local rule defined by n x n matrices with elements in Z_m which, in turn, strictly contains the class of linear CA over Z_m. In order to further emphasize that finite abelian groups are more expressive than Z_m we prove that, contrary to what happens in Z_m, there exist additive CA over suitable finite abelian groups which are roots (with arbitrarily large indices) of the shift map. As a consequence of our results, we have that, for additive CA, ergodic mixing, weak ergodic mixing, ergodicity, topological mixing, weak topological mixing, topological total transitivity and topological transitivity are all equivalent properties. As a corollary, we have that invertible transitive additive CA are isomorphic to Bernoulli shifts. Finally, we provide a first characterization of strong transitivity for additive CA which we suspect it might be t

Higher-order cellular automata (HOCA) are a variant of cellular automata (CA) used in many applications (ranging, for instance, from the design of secret sharing schemes to data compression and image processing), and in which the global state of the system at time t depends not only on the state at time t−1, as in the original model, but also on the states at time t−2, ..., t−n, where n is the memory size of the HOCA. We provide decidable characterizations of two important dynamical properties, namely, sensitivity to the initial conditions and equicontinuity, for linear HOCA over the alphabet Z m . These characterizations have an impact in applications since the involved linear HOCA are usually required to exhibit a chaotic or stable behaviour. Moreover, they extend the ones shown in [28] for linear CA (LCA) over the alphabet Z m n in the case n=1. We also show that linear HOCA of memory size n over Z m form a class that is indistinguishable from a specific subclass of LCA over Z m n . This enables to decide injectivity and surjectivity for linear HOCA of memory size n over Z m using the decidable characterization provided in [2] and [25] for injectivity and surjectivity of LCA over Z m n . Finally, we prove an equivalence between LCA over Z m n and an important class of non-uniform CA, another variant of CA used in many applications