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


Nonlinear Sciences - Cellular Automata and Lattice Gases Publications

In a recent paper [arXiv:1506.06649 [nlin.CG]], we presented an example of a 3-state cellular automaton which exhibits behaviour analogous to degenerate hyperbolicity often observed in finite-dimensional dynamical systems. Read More

Traffic breakdown, as one of the most puzzling traffic flow phenomena, is characterized by sharply decreasing speed, abruptly increasing density and in particular suddenly plummeting capacity. In order to clarify its root mechanisms and model its observed properties, this paper proposes a car-following model based on the following assumptions: (i) There exists a preferred time-varied and speed-dependent space gap that cars hope to maintain; (ii) there exists a region R restricted by two critical space gaps and two critical speeds in the car following region on the speed-space gap diagram, in which cars' movements are determined by the weighted mean of the space- gap-determined acceleration and the speed-difference-determined acceleration; and (iii) out of region R, cars either accelerate to the free flow speed or decelerate to keep safety. Simulation results show that this model is able to simultaneously reproduce traffic breakdown and the transition from the synchronized traffic flow to wide moving jams. Read More

Almost four decades ago, Gacs, Kurdyumov, and Levin introduced three different cellular automata to investigate whether one-dimensional nonequilibrium interacting particle systems are capable of displaying phase transitions and, as a by-product, introduced the density classification problem in the cellular automata literature. Their model II became a well known model in theoretical computer science and statistical mechanics. The other models, however, did not receive much attention. Read More

The search for symmetry as an unusual yet profoundly appealing phenomenon, and the origin of regular, repeating configuration patterns have been for a long time a central focus of complexity science, and physics. Here, we introduce group-theoretic concepts to identify and enumerate the symmetric inputs, which result in irreversible system behaviors with undesired effects on many computational tasks. The concept of so-called configuration shift-symmetry is applied on two-dimensional cellular automata as an ideal model of computation. Read More

The microtubule (MT) motor Kip3p is very processive kinesin that promotes catastrophes and pausing in particular on cortical contact. These properties explain the role of Kip3p in positioning the mitotic spindle in budding yeast and potentially other processes controlled by kinesin-8 family members. We present a theoretical approach to positioning of a MT network in a cell. Read More

We investigate one-dimensional elementary probabilistic cellular automata (PCA) whose dynamics in first-order mean field approximation yield discrete logistic-like growth models for a single-species unstructured population with nonoverlapping generations. Beginning with a general six-parameter model, we find constraints on the transition probabilities of the PCA that guarantee that the ensuing approximations make sense in terms of population dynamics and classify the valid combinations thereof. Several possible models display a negative cubic term that can be interpreted as a weak Allee factor. Read More

A cellular non-linear network (CNN) is a uniform regular array of locally connected continuous-state machines, or nodes, which update their states simultaneously in discrete time. A microbial fuel cell (MFC) is an electro-chemical reactor using the metabolism of bacteria to drive an electrical current. In a CNN model of the MFC, each node takes a vector of states which represent geometrical characteristics of the cell, like the electrodes or impermeable borders, and quantify measurable properties like bacterial population, charges produced and hydrogen ions concentrations. Read More

The intersecting pedestrian flow on the 2D lattice with random update rule is studied. Each pedestrian has three moving directions without the back step. Under periodic boundary conditions, an intermediate phase has been found at which some pedestrians could move along the border of jamming stripes. Read More

This paper investigates cells proliferation dynamics in small tumor cell aggregates using an individual based model (IBM). The simulation model is designed to study the morphology of the cell population and of the cell lineages as well as the impact of the orientation of the division plane on this morphology. Our IBM model is based on the hypothesis that cells are incompressible objects that grow in size and divide once a threshold size is reached, and that newly born cell adhere to the existing cell cluster. Read More

A Turmit is a Turing machine that works over a two-dimensional grid, that is, an agent that moves, reads and writes symbols over the cells of the grid. Its state is an arrow and, depending on the symbol that it reads, it turns to the left or to the right, switching the symbol at the same time. Several symbols are admitted, and the rule is specified by the turning sense that the machine has over each symbol. Read More

The interactive computation paradigm is reviewed and a particular example is extended to form the stochastic analog of a computational process via a transcription of a minimal Turing Machine into an equivalent asynchronous Cellular Automaton with an exponential waiting times distribution of effective transitions. Furthermore, a special toolbox for analytic derivation of recursive relations of important statistical and other quantities is introduced in the form of an Inductive Combinatorial Hierarchy. Read More

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 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

A novel, information-based classification of elementary cellular automata is proposed that circumvents the problems associated with isolating whether complexity is in fact intrinsic to a dynamical rule, or if it arises merely as a product of a complex initial state. Transfer entropy variations processed by the system split the 256 elementary rules into three information classes, based on sensitivity to initial conditions. These classes form a hierarchy such that coarse-graining transitions observed among elementary cellular 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