Nonlinear Sciences - Cellular Automata and Lattice Gases Publications (50)


Nonlinear Sciences - Cellular Automata and Lattice Gases Publications

Large scale, dynamical simulations have been performed for the two dimensional octahedron model, describing Kardar-Parisi-Zhang (KPZ) for nonlinear, or Edwards-Wilkinson for linear surface growth. The autocorrelation functions of the heights and the dimer lattice gas variables are determined with high precision. Parallel random sequential (RS) and two-sub-lattice stochastic dynamics (SCA) have been compared. Read More

A synopsis is offered of the properties of discrete and integer-valued, hence "natural", cellular automata (CA). A particular class comprises the "Hamiltonian CA" with discrete updating rules that resemble Hamilton's equations. The resulting dynamics is linear like the unitary evolution described by the Schr\"odinger equation. Read More

It is shown that any two cellular automata (CA) in rule space can be connected by a continuous path parameterized by a real number $\kappa \in (0, \infty)$, each point in the path corresponding to a coupled map lattice (CML). In the limits $\kappa \to 0$ and $\kappa \to \infty$ the CML becomes each of the two CA entering in the connection. A mean-field, reduced model is obtained from the connection and allows to gain insight in those parameter regimes at intermediate $\kappa$ where the dynamics is approximately homogeneous within each neighborhood. Read More

A modified lattice gas model is proposed to study pedestrian evacuation from a single room. The payoff matrix in this model represents the complicated interactions between selfish individuals, and the mean force imposed on an individual is given by considering the impacts of neighborhood payoff, walls, and defector herding. Each passer-by moves to his selected location according to the Fermi function, and the average velocity of pedestrian flow is defined as a function of the motion rule. Read More

Complex systems in a wide variety of areas such as biological modeling, image processing, and language recognition can be modeled using networks of very simple machines called finite automata. Connecting subsystems modeled using finite automata into a network allows for more computational power. One such network, called a cellular automaton, consists of an n-dimensional array for n > 1 with a single finite automaton located at each point of the array. Read More

We present a weakly coupled map lattice model for patterning that explores the effects exerted by weakening the local dynamic rules on model biological and artificial networks composed of two-state building blocks (cells). To this end, we use two cellular automata models based on: (i) a smooth majority rule (model I) and (ii) a set of rules similar to those of Conway's Game of Life (model II). The normal and abnormal cell states evolve according with local rules that are modulated by a parameter $\kappa$. Read More

We re-examine the isotropic Precursor-Rule (of the anisotropic X-Rule) and show that it is also logically universal. The Precursor-Rule was selected from a sample of biased cellular automata rules classified by input-entropy. These biases followed most "Life-Like" constraints --- in particular isotropy, but not simple birth/survival logic. Read More

A diffusive lattice gas is characterized by the diffusion coefficient depending only on the density. The Green-Kubo formula for the diffusivity can be represented as a variational formula, but even when the equilibrium properties of a lattice gas are analytically known the diffusion coefficient can be computed only in the exceptional situation when the lattice gas is gradient. In the general case, minimization over an infinite-dimensional space is required. Read More

We consider a modified Nagel-Schreckenberg (NS) model in which drivers do not decelerate if their speed is smaller than the headway (number of empty sites to the car ahead). (In the original NS model, such a reduction in speed occurs with probability $p$, independent of the headway, as long as the current speed is greater than zero.) In the modified model the free-flow state (with all vehicles traveling at the maximum speed, $v_{max}$) is {\it absorbing} for densities $\rho$ smaller than a critical value $\rho_c = 1/(v_{max} + 2)$. Read More

We investigate the speed time series of the vehicles recorded by a camera at a section of a highway in the city of Isfahan, Iran. Using $k$-means clustering algorithm, we find that the natural number of clustering for this set of data is $3$. This is in agreement with the three-phase theory of uninterrupted traffic flows. Read More

As a clear signature of modern urban design concepts, urban street networks in dense populated zones are evolving nowadays towards grid-like layouts with rectangular shapes, and most studies on traffic flow assume street networks as square lattices. However, ideas from forgotten design schools bring unexplored alternatives that might improve traffic flow in many circumstances. Inspired on an old and almost in oblivion urban plan, we report the behavior of the Biham-Middleton-Levine model (BML) \-- a paradigm for studying phase transitions of traffic flow \-- on a hypothetical city with a perfect honeycomb street network. Read More

It was recently shown how graphs can be used to provide descriptions of psychopathologies, where symptoms of, say, depression, affect each other and certain configurations determine whether someone could fall into a sudden depression. To analyse changes over time and characterise possible future behaviour is rather difficult for large graphs. We describe the dynamics of networks using one-dimensional discrete time dynamical systems theory obtained from a mean field approach to (elementary) probabilistic cellular automata (PCA). Read More

We consider the exclusion process on a ring with time-dependent defective bonds at which the hoping rate periodically switches between zero and one. This system models main roads in city traffics, intersecting with perpendicular streets. We explore basic properties of the system, in particular dependence of the vehicular flow on the parameters of signalization as well as the system size and the car density. Read More

We advance our approach of analyzing the dynamics of interacting complex systems with the nonlinear dynamics of interacting nonlinear elements. We replace the widely used lattice-like connection topology of cellular neural networks (CNN) by complex topologies that include both short- and long-ranged connections. With an exemplary time-resolved analysis of asymmetric nonlinear interdependences between the seizure generating area and its immediate surrounding we provide first evidence for complex CNN connection topologies to allow for a faster network optimization together with an improved approximation accuracy of directed interactions. Read More

Linear acceleration theorems are known for most computational models. Although such results have been proved for two-dimensional cellular automata working on specific neighborhoods, no general construction was known. We present here a technique of linear acceleration for all two-dimensional languages recognized by cellular automata working on complete neighborhoods. Read More

We study two-dimensional rotation-symmetric number-conserving cellular automata working on the von Neumann neighborhood (RNCA). It is known that such automata with 4 states or less are trivial, so we investigate the possible rules with 5 states. We give a full characterization of these automata and show that they cannot be strongly Turing universal. Read More

We undertake an investigation of combinatorial designs engendered by cellular automata (CA), focusing in particular on orthogonal Latin squares and orthogonal arrays. The motivation is of cryptographic nature. Indeed, we consider the problem of employing CA to define threshold secret sharing schemes via orthogonal Latin squares. Read More

To help mitigate road congestion, many transit authorities have implemented managed lane policies. Managed lanes typically run parallel to a freeway's standard, general-purpose (GP) lanes, but are restricted to certain types of vehicles. It was originally thought that managed lanes would improve the use of existing infrastructure through incentivization of demand-management behaviors like carpooling, but implementations have often been characterized by unpredicted phenomena that is often to detrimental system performance. Read More

Using elementary cellular automata as an example, a novel, information-based classification of complex systems is proposed that circumvents the problems associated with isolating the complexity generated as a product of an initial state from that which is intrinsic to a dynamical rule. Transfer entropy variations processed by the system for different initial states split the 256 elementary rules into three information classes. These classes form a hierarchy such that coarse-graining transitions permitted among automata rules predominately occur within each information-based class, or much more rarely down the hierarchy. Read More

Local Scale-Invariance theory is tested by extensive dynamical simulations of the driven dimer lattice gas model, describing the surface growth of the 2+1 dimensional Kardar-Parisi-Zhang surfaces. Very precise measurements of the universal autoresponse function enabled us to perform nonlinear fitting with the scaling forms, suggested by local scale-invariance (LSI). While the simple LSI ansatz does not seem to work, forms based on logarithmic extension of LSI provide satisfactory description of the full (measured) time evolution of the autoresponse function. Read More

A cellular automaton collider is a finite state machine build of rings of one-dimensional cellular automata. We show how a computation can be performed on the collider by exploiting interactions between gliders (particles, localisations). The constructions proposed are based on universality of elementary cellular automaton rule 110, cyclic tag systems, supercolliders, and computing on rings. Read More

In this work we present a model for the evacuation of pedestrians from an enclosure considering a continuous space substrate and discrete time. We analyze the influence of behavioral features that affect the use of the empty space, that can be linked to the attitudes or characters of the pedestrians. We study how the interaction of different behavioral profiles affects the needed time to evacuate completely a room and the occurrence of clogging. Read More

The Nagel-Schreckenberg model with overtaking strategy (NSOS) is proposed, and numerical simulations are performed for both closed and open boundary conditions. The fundamental diagram, space-time diagram, and spatial-temporal distribution of speed are investigated. In order to identify the synchronized flow state, both the correlation functions (autocorrelation and cross-correlation) and the one-minute average flow rate vs. Read More

We propose and analyze extended floor field cellular automaton models for evacuation dynamics of inhomogeneous pedestrian pairs which are coupled by asymmetric group interactions. Such pairs consist of a leader, who mainly determines the couple's motion and a follower, who has a defined tendency to follow the leader. Examples for such pairs are mother and child or two siblings of different age. Read More

We study the Braess paradox in the transport network as originally proposed by Braess with totally asymmetric exclusion processes (TASEPs) on the edges. The Braess paradox describes the counterintuitive situation in which adding an edge to a road network leads to a user optimum with higher travel times for all network users. Travel times on the TASEPs are nonlinear in the density, and jammed states can occur due to the microscopic exclusion principle, leading to a more realistic description of trafficlike transport on the network than in previously studied linear macroscopic mathematical models. Read More

Affiliations: 1Istituto di Scienza e Tecnologie dell'Informazione "A. Faedo", Consiglio Nazionale delle Ricerche, 2Istituto di Scienza e Tecnologie dell'Informazione "A. Faedo", Consiglio Nazionale delle Ricerche

The emerging field of Nominal Computation Theory is concerned with the theory of Nominal Sets and its applications to Computer Science. We investigate here the impact of nominal sets on the definition of Cellular Automata and on their computational capabilities, with a special focus on the emergent behavioural properties of this new model and their significance in the context of computation-oriented interpretations of physical phenomena. A preliminary investigation of the relations between Nominal Cellular Automata and Wolfram's Elementary Cellular Automata is also carried out. Read More

A master equation approach is applied to a reversible and conservative cellular automata model (Q2R). The Q2R model is a dynamical variation of the Ising model for ferromagnetism that possesses quite a rich and complex dynamics. The configurational space is composed by a huge number of cycles with exponentially long periods. Read More

The original local, discrete example of Linear Unitary Cellular Automata (LUCA) is analyzed in terms of a new representation previously introduced in [1] for classical CA. Several important underlying symmetries are reviewed and their tight relationship with both signal and coding theory as well as with combinatorics is underlined. A class of analog implementations in the form of Linear Transmission Line Networks (LTLN) is described as possible emulators of this type of dynamics. Read More

The purpose of the present study is to search one-dimensional Cellular Automata (CA) rules which will solve the density classification task (DCT) perfectly. The mathematical analysis of number conserving functions over binary strings of length n gives an indication of its corresponding number conserving cellular automata rules (either uniform or non-uniform). The state transition diagrams (STDs) of number conserving CA rules have been analyzed where it has been found that these STDs can generate different DCT solutions. Read More

Periodically-driven quantum systems can exhibit topologically non-trivial behaviour, even when their quasi-energy bands have zero Chern numbers. Much work has been conducted on non-interacting quantum-mechanical models where this kind of behaviour is present. However, the inclusion of interactions in out-of-equilibrium quantum systems can prove to be quite challenging. Read More

One successful model of interacting biological systems is the Boolean network. The dynamics of a Boolean network, controlled with Boolean functions, is usually considered to be a Markovian (memory-less) process. However, both self organizing features of biological phenomena and their intelligent nature should raise some doubt about ignoring the history of their time evolution. Read More

Cellular automata (CAs) are dynamic frameworks which exhibit complex global behavior from simple local interaction and computation. Since the inception of CA by von Neumann in $1950$s, it has attracted the attention of several researchers over various backgrounds and fields for modeling different physical, natural as well as real-life phenomena. Classically, CAs are uniform. Read More

Open-ended evolution (OEE) is relevant to a variety of biological, artificial and technological systems, but has been challenging to reproduce in silico. Most theoretical efforts focus on key aspects of open-ended evolution as it appears in biology. We recast the problem as a more general one in dynamical systems theory, providing simple criteria for open-ended evolution based on two hallmark features: unbounded evolution and innovation. Read More

An interesting problem in extended physical systems is that of the regional control, i.e., how to add a suitable control at the boundary or inside a region of interest so that the state of such region is near to a desired one. Read More

In this paper, we construct a weakly universal cellular automaton on the tessellation $\{8,3\}$ which is not rotation invariant but which is truly planar. Read More

One of the simplest multilevel cellular automata - the hodgepodge machine - was modified to best match the chemical trajectory observed in the Belousov-Zhabotinsky reaction. Noise introduces watersheding of the central regular pattern into the circular target pattern. This article analyzes influences of the neighborhood and internal excitation kinds of noise. Read More

We present a spectral representation of any computation performed by a Cellular Automaton (CA) of arbitrary topology and dimensionality via an appropriate coding scheme in Fourier space that can be implemented in an analog machine ideally circumventing part of the overall waste heat production. We explore further consequences of this encoding and we provide a simple example based on the Game-of-Life where we find global maps for small lattices indicating an interesting underlying recursive structure. Read More

A major hurdle in the simulation of the steady state of epidemic processes is that the system will unavoidably visit an absorbing, disease-free state at sufficiently long times due to the finite size of the networks where epidemics evolves. In the present work, we compare different quasistationary (QS) simulation methods where the absorbing states are suitably handled and the thermodynamical limit of the original dynamics can be achieved. We analyze the standard QS (SQS) method, where the sampling is constrained to active configurations, the reflecting boundary condition (RBC), where the dynamics returns to the pre-absorbing configuration, and hub reactivation (HR), where the most connected vertex of the network is reactivated after a visit to an absorbing state. Read More

In this paper, we construct a weakly universal cellular automaton on the tessellation $\{9,3\}$ which has two states and which is not rotation invariant but which is truly planar. Read More

We explore the emergence of persistent infection in a patch of population, where the disease progression of the individuals is given by the SIRS model and an individual becomes infected on contact with another infected individual. We investigate the persistence of contagion qualitatively and quantitatively, under varying degrees of heterogeneity in the initial population. We observe that when the initial population is uniform, consisting of individuals at the same stage of disease progression, infection arising from a contagious seed does not persist. Read More

We present a diagrammatic method to build up sophisticated cellular automata (CAs) as models of complex physical systems. The diagrams complement the mathematical approach to CA modeling, whose details are also presented here, and allow CAs in rule space to be classified according to their hierarchy of layers. Since the method is valid for any discrete operator and only depends on the alphabet size, the resulting conclusions, of general validity, apply to CAs in any dimension or order in time, arbitrary neighborhood ranges and topology. Read More

The complexity of human behaviour can lead to very unpredictable patterns in social activity and structure. Here we demonstrate the instability of a community network controlled by majority ruling, where an element adopts the most popular opinion of their peers. We modelled a community as a square lattice, and performed sequential time step numerical calculations upon each cell in parallel. Read More

The misanthrope process is a class of stochastic interacting particle systems, generalizing the simple exclusion process. It allows each site of the lattice to accommodate more than one particle. We consider a special case of the one dimensional misanthrope process whose probability distribution is completely equivalent to the ordinary simple exclusion process under the periodic boundary condition. Read More

We discuss various properties of Probabilistic Cellular Automata, such as the structure of the set of stationary measures and multiplicity of stationary measures (or phase transition) for reversible models. Read More

For a general attractive Probabilistic Cellular Automata on S Z d , we prove that the (time-) convergence towards equilibrium of this Markovian parallel dynamics, exponentially fast in the uniform norm, is equivalent to a condition (A). This condition means the exponential decay of the inuence from the boundary for the invariant measures of the system restricted to nite boxes. For a class of reversible PCA dynamics on {--1, +1} Z d , with a naturally associated Gibbsian potential $\varphi$, we prove that a (spatial-) weak mixing condition (WM) for $\varphi$ implies the validity of the assumption (A); thus exponential (time-) ergodicity of these dynamics towards the unique Gibbs measure associated to $\varphi$ holds. Read More

Cellular automata can show well known features of quantum mechanics, such as a linear rule according to which they evolve and which resembles a discretized version of the Schroedinger equation. This includes corresponding conservation laws. The class of "natural" Hamiltonian cellular automata is based exclusively on integer-valued variables and couplings and their dynamics derives from an Action Principle. Read More

The density classification problem is the computational problem of finding the majority in a given array of votes in a distributed fashion. It is known that no cellular automaton rule with binary alphabet can solve the density classification problem. On the other hand, it was shown that a probabilistic mixture of the traffic rule and the majority rule solves the one-dimensional problem correctly with a probability arbitrarily close to one. Read More

Cellular automata can show well known features of quantum mechanics, such as a linear updating rule that resembles a discretized form of the Schr\"odinger equation together with its conservation laws. Surprisingly, a whole class of "natural" Hamiltonian cellular automata, which are based entirely on integer-valued variables and couplings and derived from an Action Principle, can be mapped reversibly to continuum models with the help of Sampling Theory. This results in "deformed" quantum mechanical models with a finite discreteness scale $l$, which for $l\rightarrow 0$ reproduce the familiar continuum limit. Read More