1,721,108 research outputs found
Reaction systems and extremal combinatorics properties
No full textExtremal 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 combinatorics. We define several different properties that capture some basic and dynamical behaviors of a reaction system and we prove that they must necessarily be satisfied if the system is large enough. Explicit bounds and formulae are also provided
An Easy to Check Characterization of Positive Expansivity for Additive Cellular Automata over a Finite Abelian Group
Full text linkAdditive cellular automata over a finite abelian group are a wide class of cellular automata (CA) that are able to exhibit most of the complex behaviors of general CA and they are often exploited for designing applications in different practical contexts. We provide an easy to check algebraic characterization of positive expansivity for Additive Cellular Automata over a finite abelian group. We stress that positive expansivity is an important property that defines a condition of strong chaos for CA and, for this reason, an easy to check characterization of positive expansivity turns out to be crucial for designing proper applications based on Additive CA and where a condition of strong chaos is required. First of all, in the paper an easy to check algebraic characterization of positive expansivity is provided for the non trivial subclass of Linear Cellular Automata over the alphabet (Z/mZ)n . Then, we show how it can be exploited to decide positive expansivity for the whole class of Additive Cellular Automata over a finite abelian group
An Efficient Algorithm Deciding Chaos for Linear Cellular Automata over (Z/mZ)n with Applications to Data Encryption
Full text linkWe provide an efficient algorithm deciding chaos for linear cellular automata (LCA) over (Z/mZ)^n, a large and important class of cellular automata (CA) which may exhibit many of the complex features typical of general CA and are used in many applications. The efficiency of our algorithm is mainly due to fact that it avoids the computation of the prime factor decomposition of m which is a well-known difficult task. Instead of factoring m we make use of a new and efficient generalized technique for computing the greatest common divisor (gcd) of polynomials with coefficients not belonging to a field, which in itself is an interesting result. We wish also to emphasize that the gcd computations required by our algorithm always involve polynomials of degree at most n. We also illustrate the impact of our algorithm in real-world applications regarding the growing domain of cryptosystems, the latter being often based on LCA over (Z/mZ)^n with n>1. As a matter of facts, since cryptosystems have to satisfy the so-called confusion and diffusion properties (which are ensured if the involved LCA is chaotic) our algorithm turns out to be an important tool for building chaotic LCA over (Z/mZ)^n and, hence, for improving the existing methods based on them
On the Dynamical Behavior of Cellular Automata on Finite Groups
Full text linkDuring the last few decades, significant efforts have been devoted to analyze the dynamical behavior of cellular automata (CAs) on cyclic groups, their Cartesian power (referred to as linear cellular automata), and on general abelian groups (referred to as additive cellular automata). Many fundamental properties describing the dynamical behavior of a system such as injectivity, surjectivity, sentitivity to the initial conditions, topological transitivity, ergodicity, positive expansivity, denseness of periodic orbits, and chaos have been fully characterized for these classes of cellular automata, i.e., the relation between the cellular automaton (CA) local rule and the CA global behavior was made explicit, being this task a challenging and important problem in CA general theory. A natural step forward leads to investigate the dynamical behavior of group cellular automata, i.e., cellular automata defined on (not necessarily abelian) finite groups. Despite the work recently carried out by some authors, none of the previously mentioned properties has yet been fully characterized in the case of general finite groups. In this paper, we study the dynamical behavior of cellular automata on a number of classes of finite groups such as simple, symmetric, alternating, dihedral, quaternion and decomposable groups and we provide exact characterizations for some of the above mentioned properties. To do this, in each of those classes, we focus our attention to the non-abelian scenarios. Some results are quite surprising because they show that the non-abelianness of the group imposes strong limitations on defining the local rule of the cellular automaton, making the class of group cellular automata very constrained. Finally, we also introduce a graph allowing one to build and study the local rules of any group cellular automaton
Computing issues of asynchronous CA
No full textThis 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
Decidable Characterizations of Dynamical Properties for Additive Cellular Automata over a Finite Abelian Group with Applications to Data Encryption
Full text linkAdditive cellular automata over a finite abelian group are a wide class of cellular automata (CA) that are able to exhibit the complex behaviors of general CA and are often exploited for designing applications in different practical contexts. We provide decidable characterizations for Additive CA of the following important properties defining complex behaviors of complex systems: injectivity, surjectivity, equicontinuity, sensitivity to the initial conditions, topological transitivity, and ergodicity. Since such properties describe the main features required by real systems, the decision algorithms from our decidability results are then important tools for designing proper applications based on Additive CA. Indeed, we describe how our results can be exploited in some emblematic applications of cryptosystems, a paradigmatic and nowadays crucial applicative domain in which Additive CA are extensively used. We deal with methods for data encryption and, namely, we propose some strong modifications to the existing schemes in order to increase their security level and make attacks much harde
Ancestors, descendants, and gardens of Eden in reaction systems
No full textThis paper analyses several problems related to finding and counting ancestor and descendant states, as well as gardens of Eden (i.e., states without predecessors) in reaction systems. The focus is on the complexity of finding and counting preimages and ancestors that are minimal with respect to cardinality. It turns out that the problems concerning gardens of Eden seem to require the presence of an NP-oracle to be solved. All the problems studied are intractable, with a complexity that ranges form FP^NP[log n] to FPSPACE(poly)
An efficiently computable characterization of stability and instability for linear cellular automata
Full text linkWe provide an efficiently computable characterization of two important properties describing stable and unstable complex behaviours as equicontinuity and sensitivity to the initial conditions for one-dimensional linear cellular automata (LCA) over (Z/mZ)^n. We stress that the setting of LCA over (Z/mZ)^n with n>1 is more expressive, it gives rise to much more complex dynamics, and it is more difficult to deal with than the already investigated case n=1. Indeed, in order to get our result we need to prove a nontrivial result of abstract algebra: if K is any finite commutative ring and L is any K-algebra, then for every pair A, B of nxn matrices over L having the same characteristic polynomial, it holds that the set {A^0,A^1,A^2,...} is finite if and only if the set {B^0,B^1,B^2,...} is finite too
Pure reaction automata
Full text linkThis work introduces the new class of pure reaction automata, as well as a new update manner, called maximal reactive manner, that can also be applied to standard reaction automata. Pure reaction automata differ from the standard model in that they don't have permanence: the entities that are not consumed by the reactions happening at a certain state are not conserved in the result states.
We prove that the set of languages accepted by the new class under the maximal reactive manner contains the set of languages accepted by standard reaction automata under the same manner or under the maximal parallel manner. We also prove that a strict subclass of pure reaction automata can compute any partial recursive function
Dynamical behavior of additive cellular automata over finite abelian groups
No full textWe study the dynamical behavior of additive D-dimensional (
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 [38], [44], [41]. Among our major contributions, there is the proof that topologically transitive additive D-dimensional cellular automata over a finite abelian group are ergodic. This result represents a solid bridge between the world of measure theory and that of topology and greatly extends previous results obtained in [12], [44] for linear CA over
, i.e., additive CA in which the alphabet is the cyclic group
and the local rules are linear combinations with coefficients in
. 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
, i.e., with the local rule defined by
matrices with elements in
which, in turn, strictly contains the class of linear CA over
. In order to further emphasize that finite abelian groups are more expressive than
we prove that, contrary to what happens in
, there exist additive CA over suitable finite abelian groups which are roots (with arbitrarily large indices) of the shift map.
As a relevant consequence of our results, we have that, for additive D-dimensional CA over a finite abelian group, 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 see that invertible transitive additive CA are isomorphic to Bernoulli shifts. Furthermore, we prove that surjectivity implies openness for additive D-dimensional CA over a finite abelian group. Hence, we get that topological transitivity is equivalent to the well-known Devaney notion of chaos when
. Moreover, we provide a first characterization of strong transitivity for additive CA which we suspect to be true also for the general case
- …
