Abstract: A one-parameter family of transformations defined on the set of all one-dimensional cellular automata is studied. the class of a given cellular automaton is unchanged under the set of these transformations. For class-3 cellular automata, transformed statistical quantities satisfy simple scaling properties.
(return to Contents)
Abstract: A mean-field theory of (probabilistic) cellular automata is developed and used to to select a typical local rule whose mean-field analysis predicts first-order phase transitions. The corresponding automaton is then studied numerically on regular lattices for space dimensions d between 1 and 4. At odds with usual beliefs on two-state automata with one absorbing phase, first-order transitions are indeed exhibited as soon as d>1, with closer quantitative agreement with mean-field predictions for high space dimensions. For d=1, the transition is continuous, but with critical exponent different from those of directed percolation.
(return to Contents)
N. Boccara, J. Nasser
and M. Roger, Annihilation of Defects during the Evolution
of Some One-Dimensional Class-3 Deterministic Cellular Automata,
Europhys. Lett. 13 (6) 489-494 (1990)
Abstract: For some class-3 cellular automata, probability distribution of sequences of zeros and ones for cenfigurations belonging to the attractor are determined. Defects, which exist in configurations not belonging to the attractor, combine between themselves according to simple laws.
(return to Contents)
Abstract: Given a one-dimensional cellular automaton rule f, a block transform of f is a rule T(b)f such that there exists between the limit sets of both rules a bijection that replaces each site value x in a configuration belonging to the limit set of f with a string xxx...x of length b in the corresponding configuration belonging to the limit set of T(b)f. If f is totalistic, there exists a unique totalistic block transform and a large number of nontotalistic block transforms T(b)f. If f is not totalistic, there are no totalistic block transforms but there still exists a large number of nontotalistic block transforms. Their number increases very rapidly with the block size b and the range r of f. The range of T(b)f may be any integer greater than or equal to rb. Many block transform are studied. The evolution according to rule T(b)f towards its limit set is discussed in terms of the annihilation of defects. These defects are often simply related to the defects characterizing the evolution according to rule f.
(return to Contents)
Abstract: Configurations generated by the evolution of some one-dimensional cellular automata may be vieved, after many time steps, as particlelike structures evolving in a regular background. A classification of the most frequently observed "particles" is proposed according to their specific behavior. The simplest - a straightforward generalization of the "kinks" in range-1 Rule 18 earlier studied by Grassberger [Phys. Rev. A 28, 3666 (1993)] - exhibit a diffusive motion and annihilate according to simple processes. Others have, in contrast, constant (positive, negative or zero) velocities. The "collision" of particles with different velocities leads to some "reactions" in which some particles are annihilated and others are created. A detailed desription of such "reactions" sheds new light on the large-time behavior of range-1 rule 54 with a very slow decrease of the particular number. More "exotic" behaviors are sometimes observed. Some particlelike structures radiate other "particles". Some "particles" combine to generate a perturbation whose space extension increases with time and can be annihilated through the interaction with other "particles". these different behaviors could lead to a more precise classification of cellular-automata rules.
(return to Contents)
N. Boccara and M. Roger,
Period-Doubling Route to Chaos for a Global Variable of a
Probabilistic Automata Network J. Phys. A: Math. Gen. 25
L1009-L1014 (1992)
Abstract: As a function of a parameter characterizing the degree of mixing of site values, the density of non-zero sites of some one-dimensional cellular automata is shown to exhibit a sequence of period-doubling bifurcations and to behave chaotically whn the degree of mixing is sufficiently large. The automata network rules which are considered appear to be useful to model complex systems, as in epidemiology, in which the motion of the individuals is believed to play an important role.
(return to Contents)
Abstract: If M is a noninvertible translation-invariant local surjective mapping, it is shown that some local one-dimensional deterministic cellular automaton rules F have a transform F' by M defined by F'M=MF'. When it exist F' is local and its Wolfram's class is the same as F. The evolution of a cellular automaton according to rule F' is simply related to the evolution according to rule F. In the case of class-3 rules, the evolution to the attractor may often be viewed as particle-like structures evolving in a regular background. If the structure of these particles and their interactions for a rule F are known, then the structure and interactions of the transformed particles for the rule F' are also known. If M is a nontrivial invertible translation-invariant local surjective mapping,F' always exists, but it is, in general, site- and time-dependent.
(return to Contents)
N. Boccara and M. Roger,
Site-Exchange Cellular Automata in Instabilities and
Nonequilibrium Structures IV, E. Tirapegui and W. Zeller eds.
109-118 (Dordrecht: Kluwer 1993)
Abstract: We study the stationary density of nonzero sites of automata networks whose local rule consists of two subrules. The first one, applied synchronously, is a one-dimensional range-one cellular automaton rule. The second, applied sequentially, mixes the site values. The mixing results from either a local or a nonlocal exchange of the site values.
(return to Contents)
Abstract: The effect of mixing on one-imensional probabilistic cellular automaton with totalistic rule has been investigated by different methods. The evolution of the system depends on two parameters, the probability p and the degree of mixing m. The two- dimensional phase space of parameters has been explored by simulation. The results are compared to the multiple-point- correlation approximation. By increasing the mixing, the order of the phase transition has been found to change from second order to first order. The tricritical point has been located and estimateds are given for the beta exponent. Short- and long-range mixing are compared.
(return to Contents)
F. Bagnoli, N. Boccara
and P. Palmerini, Phase Transitions in a Probabilistic
Cellular Automaton with Two Absorbing States, Lecture notes
of the Summer School on Biotechnology held at Torino (Italy) in
June 1996, (Singapore: World Scientific, 1998)
Abstract: We study the phase diagram and the critical behavior
of a one-dimensional radius-1 two-state totalistic probabilistic cellular
automaton having two absorbing states. This system exhibits a first-order
phase transition between the fully occupied state and the empty state, two
second-order phase transitions between a partially occupied state and either
the fully occupied state or the empty state, and a second-order damage spreading
phase transition. It is found that all the second-order phase transitions
have the same critical behavior as the directed percolation model. The mean-field
approximation gives a rather good qualitative description of all these phase
transitions.
Click here to download
this paper from the xxx archive.
(return to Contents)
N. Boccara, Automata
Network Models of Interacting Populations in Cellular Automata,
Dynamical Systems and Neural Networks, E. Goles and S. Martinez
eds 23-78 (Dordrecht: Kluwer 1994)
Abstract: This series of lectures is devoted to the investigation of models of interacting populations such as susceptibles and infectives in epidemiology or competing species in ecology. The different models to be discussed are extensions of the so-called "general epidemic model." In this model, infection spreads by contact from infectives to susceptibles, and infectives are removed from circulation by death or isolation. The various models to be described are formulated in terms of site-exchange cellular automata, which take into account the local character of the infection process and the motion of individuals.
(return to Contents)
N. Boccara, H. Fukś,
S. Geurten A New Class of Automata Networks, Physica
D 103
145-154 (1997)
Abstract: A new class of automata networks
is defined. Their evolution rules are determined by a probability
measure p on the set of all integers Z and an indicator
function I_A on the interval [0,1]. It is shown that any
cellular automaton rule can be represented by a (nonunique)
rule formulated in terms of a pair (p,I_A). This new class
of automata networks contains discrete systems which are not cellular
automata. Some of their properties are discussed.
Click here to download
this paper from xxx archive.
(return to Contents)
N. Boccara, J. Nasser
and M.Roger, Critical Behavior of a Probabilistic Local
and Nonlocal Site-Exchange Cellular Automaton Int. J. Mod. Phys.
C 5 (3) 537-545 (1994)
Abstract: We study the critical behavior of a probabilistic automata network whose local rule consists of two subrules. The first one, applied synchronously, is a probabilistic one-dimensional range-one cellular automaton rule. The second, applied sequentially, exchanges the values of a pair of sites. According to whether the two sites are first-neighbors or not, the exchange is said to be local or nonlocal. The evolution of the system depends upon two parameters, the probability p characterizing the probabilistic cellular automaton, and the degree of mixing m resulting from the exchange process. Depending upon the values of these parameters, the system exhibits a bifurcation similar to a second order phase transition characterized by a nonnegative order parameter, whose role is played by the stationary density of occupied sites. When m is very large, the correlations created by the application of the probabilistic cellular automaton rule are destroyed, and, as expected, the behavior of the system is then correctly described by a mean-field-type approximation. According to whether the exchange of the sites values is local or nonlocal, the critical behavior is qualitatively different as m varies.
(return to Contents)
N. Boccara and M. Roger,
Some Properties of Local and Nonlocal Site-Exchange Deterministic
Cellular Automata, Int. J. Mod. Phys. C 5 (3) 581-588
(1994)
Abstract: Stationary densities of nonzero sites of one-dimensional range-one deterministic cellular automata are shown to be functions of a parameter m characterizing the degree of mixing of site values. The mixing results from either local or a nonlocal exchange of the site values. In particular, the asymptotic behavior of the stationary densities of nonzero sites for very small and very large values of the parameter m have been determined.
(return to Contents)
N. Boccara and K. Cheong,
Automata Network SIR Models for the Spread of Infectious
Diseases in Populations of Moving Individuals, J. Phys.
A: Math. Gen. 25 2447-2461 (1992)
Abstract: Automata networks SIR models for the spread of infectious diseases are studied. The local rule consist of two subrules. The first one, applied sequentially, describes the motion of individuals, the second is synchronous and models infection and removal (or recovery). The spatial correlations created by the application of the second subrule are partially destroyed according to the degree of mixing of the population which follows from application of the first subrule. One- and two-population models are considered. In the second case, individuals belonging to one population may be infected only by individuals belonging to the other population as in the case, for example, for the heterosexual propagation of a venereal disease. It is shown that the occurrence of the epidemic in one population may be triggered by the occurrence of the epidemic in the other population. The emphasis is on the influence of the degree of mixing of the individuals which follows from their diffusive motion. In particular, the asymptotic behaviours for very small and very large mixing are determined. When the degree of mixing tends to infinity the correlations are completely destroyed and the time evolution of the epidemic is then correctly predicted by the mean-filed approximation.
(return to Contents)
Abstract: A probabilistic automata network SIS model for the spread
of an infectious disease in a population of moving individuals
is studied. The local rule consist of two subrules. The first
one, applied synchronously, models infection and recovery. It
is a probabilistic cellular automaton rule. The second, applied
sequentially, describes the motion of the individuals. The model
contains three parameters, the probabilities Pi to get infected
and Pr to recover, and the average number of tentative moves
per individual m. Depending upon the values of these parameters,
in the infinite-time limit, the system is either in the disease-free
state or in the endemic state. It goes from one state to the other
through a transcritical bifurcation similar to a second order phase
transition characterized by a non- negative order parameter, whose role
is played, in this model, by the stationary density of infected individuals.
The (Pi,Pr) phase diagram and the critical behaviour of the stationary
density of infectives in the neighbourhood of the phase transition, are
studied as a function of m. According to whether the individuals
perform short- or long-range moves, it is found that the parameters characterizing
the transition have a qualitatively different behaviour as m
varies. When m is very large, the correlations created by the
application of the subrule modelling infection and recovery are destroyed,and,
as expected, the behaviour of the system is then correctly predicted by
a mean- field-type approximation which assumes a homogeneous mixing of
the individuals. When m is not large, this assumption is no longer
correct.
Click
here to download this paper from IOP Web site.
(return to Contents)
Abstract: A probabilistic automata network model for the spread
of an infectious disease in a population of moving individuals
is studied. The local rule consist of two subrules. The first
one, applied synchronously, models infection, birth and death
processes. It is a probabilistic cellular automaton rule. The
second, applied sequentially, describes the motion of the individuals.
The model contains six parameters: the probabilities P for
a susceptible to become infected by a contact with an infective;
the respective birth rates Bs and Bi of the susceptibles
from either a susceptible or an infective parent; the respective death
rates Ds and Di od susceptibles and infectives; and a parameter
m characterizing the motion of the individuals. The model has
three fixed points. The first is trivial, it describes a stationary
state with no living individuals. The second corresponds to a disease-free
state with no infectives. The third and last one characterizes an endemic
state with non-zero densities of susceptibles and infectives. Moreover,
the model may exhibit oscillatory behaviour of the susceptible and
infective densities as function of time through a Hopf-type bifurcation.
The influence of the different parameters on the stability of all these
states is studied with a particular emphasis on the influence of motion
which has been found to be a stabilizing factor of the cyclic behaviour.
Click
here to download this paper from IOP Web site.
(return to Contents)
Abstract: We consider a two dimensional cellular automata whose
rule consist of the subrules. The first, applied synchronously,
is a local rule inspired from the "Game of life", with a larger
neighborhood. The second one, applied sequentially, describes
the motion of a fraction m of individuals (nonzero sites).
Such rules appear to be useful to model complex systems, as in
epidemiology, in which the motion of the individuals is believed
to play an important role. If the motion is long-range, the density
of individuals exhibits a sequence of period doubling bifurcations
and behaves chaotically when m is large enough. If the motion
is short- range (restricted to first neighbors), spatial coherence
is lost. Spatial correlations decay with a finite correlation length
of order of square root of m. We observe the formation of
domains, of mean width = correlation length, with a chaotic behavior
of the local density of nonzero sites, but the collective behavior
is stationary (the global density tends to a fixed value when the lattice
size is much larger than the square of correlation length).
Click
here to download this paper from IOP Web site.
(return to Contents)
Abstract: An automata network predator-prey model with pursuit and evasion is studied. the local rule consist of two subrules. The first one applied synchronously, models predation, birth and death processes. The second, applied sequentially, describes predator pursuit to catch evading preys. The model contains six parameters: the respective birth and death rates of preys and predators and two parameters characterizing the motion of preys and predators respectively. The model has three fixed points. The first one is trivial, it corresponds to a stationary state with no living individuals. The second one characterizes a state with no predators. The third one describes a state with nonzero densities of preys and predators. Moreover, the model may exhibit oscillatory behavior of the local prey and predator densities as function of time through a Hopf bifurcation. In this special case spatial coherence is lost. Spatial correlations decay with a finite correlation length. Although local densities, measured over a range of correlation length oscillate, collective variables are stationary.
(return to Contents)
N. Boccara and H. Fukś,
Modeling Diffusion of Innovations with Probabilistic Cellular
Automaton, Lecture notes of the Spring School on Cellular
Automata held at Saissac (France) in June 1996 (Dordrecht: Kluwer 1998)
Abstract: We present a family of one-dimensional cellular automata
modeling the diffusion of an innovation in a population.
Starting from simple deterministic rules, we construct models
parametrized by the interaction range and exhibiting a second-order
phase transition. We show that the number of individuals who
eventually keep adopting the innovation strongly depends on connectivity
between individuals.
Click here to download
this paper from xxx archive.
(return to Contents)
P. Manneville, N. Boccara,
G.Y. Vichniac and R. Bidaux eds. Cellular Automata and Modeling
of Complex Physical Systems, (Heidelberg: Springer-Verlag
1989)
Abstract: Cellular automata are fully discrete dynamical systems with dynamical variables defined at the nodes of a lattice ant taking values in a finite set. Application of a local transition rule at each lattice site generates the dynamics. The interpretation of systems with a large number of degrees of freedom in terms of lattice gases has received considerable attention recently due to the many applications of this approach, e.g. for simulating fluid flows under nearly microscopic natural phenomena such as diffusion- reaction catalysis, and for analysis of pattern-forming systems. the discussion in this book covers aspects of cellular automata theory related to general problems of information theory and statistical physics, lattice gas theory, direct applications, problems arising in the modeling of microscopic physical processes, complex macroscopic behavior (mostly in connection with turbulence), and the design of special-purpose computers.
(return to Contents)
N. Boccara, E. Goles,
S. Martínez and P. Picco eds. Cellular Automata
and Cooperative Systems, (Dordrecht: Kluwer 1993)
Abstract: This book contains the lectures given at the NATO ASI 910820 "Cellular Automata and Cooperative Systems" meeting which was held at the Centre de Physique des Houches, France, from June 22 to July 2, 1992. This workshop brought together mathematical physicists, theoretical physicists and mathematicians working in the fields related to local interacting systems, deterministic and probabilistic cellular automata, statistical physics, and complexity theory, as well as applications of these fields.
(return to Contents)
H. Fukś and N. Boccara,
Cellular Automata Models for Diffusion of Innovations,
to be published in proceeding of Sixth Meeting on Instabilities
and Nonequilibrium Structures, Santiago, Chile, 1995.
Abstract: We propose a probabilistic cellular automata model for
the spread of innovations, rumors, news, etc. in a social
system. The local rule used in the model is outertotalistic,
and the range of interaction can vary. When the range $R$ of the
rule increases, the takeover time for innovation increases and converges
toward its mean-field value, which is almost inversely proportional
to $R$ when $R$ is large. Exact solutions for $R=1$ and $R=\infty$
(mean-field) are presented, as well as simulation results for other
values of $R$. The average local density is found to converge to a
certain stationary value, which allows us to obtain a semi-phenomenological
solution valid in the vicinity of the fixed point $n=1$ (for large
$t$).
Click here to download
this paper from xxx archive.
(return to Contents)
H. Fukś and N. Boccara,
Generalized Deterministic Traffic Rules, Int. J. Phys.
C C 9 1-12 (1998)
Abstract: We study a family of deterministic models for highway
traffic flow which generalize cellular automaton rule 184.
This family is parametrized by the speed limit $m$ and another
parameter $k$ that represents a ``degree of aggressiveness''
in driving, strictly related to the distance between two consecutive
cars. We compare two driving strategies with identical maximum
throughput: ``conservative'' driving with high speed limit and
``aggressive'' driving with low speed limit. Those two strategies
are evaluated in terms of accident probability. We also discuss fundamental
diagrams of generalized traffic rules and examine limitations of maximum
achievable throughput. Possible modifications of the model are considered.
Click here to download
this paper from xxx archive.
Click here
to download this paper from World Scientific Web site
(return to Contents)
Abstract: Within the framework of a simple model of car traffic
on a one-lane highway, we study the probability for car
accidents to occur when drivers do not respect the safety
distance between cars, and, as a result of the blockage during
the time $T$ necessary to clear the road, we determine the number
of stopped cars as a function of car density. We give a simple
theory in good agreement with our numerical simulations.
Click here to download
this paper from xxx archive.
Click
here to download this paper from IOP Web site.
(return to Contents)
Abstract: After a presentation of some classical models formulated in terms of differential equations, various automata network models describing more correctly the local character of the interactions (infection or predation) are presented. One essential feature of all these models is the fact that the motion of the individuals is explicitely taken into account and shown to play an important role. The bibliography contains many reference books and all the original papers presented in the lecture.
(return to Contents)
Abstract: This paper shows how to determine all the unidimensional
two-state cellular automaton rules of a given number of
inputs which conserve the number of active sites. These rules
have to satisfy a necessary and sufficient condition. If the active
sites are viewed as celles occupied by identical particles, these
cellular automaton rules represent evolution operators of systems
of identical interacting particles whose total number is conserved.
Some of these rules, which allow motion in both directions, mimic
ensembles of one-dimensional pseudo-random walkers. Numerical evidence
indicates that these walks might be non-Gaussian.
Click here to download
this paper from xxx archive.
Click
here to download this paper from IOP Web site.
Click here
for a Java applet illustrating some results of this paper.
(return to Contents)
Abstract: We have determined families of two-dimensional deterministic
totalistic cellular automaton rules
whose stationary density of active sites
exhibits a period two in time. Each family of deterministic
rules is characterized by an ``average probabilistic totalistic
rule'' exhibiting the same periodic behavior.
Click here to download
this paper from xxx archive.
(return to Contents)
Abstract: We study a family of correlated one-dimensional random
walks with a finite memory range M. These walks are extensions
of the Taylor's walk as investigated by Goldstein, which has
a memory range equal to one. At each step, with a probability
p, the random walker moves either to the right or to the left with
equal probabilities, or with a probability q=1-p performs a move,
which is a stochastic Boolean function of the M previous steps. We
first derive the most general form of this stochastic Boolean function,
and study some typical cases which ensure that the average value <R_n>
of the walker's location after n steps is zero for all values of n.
In each case, using a matrix technique, we provide a general method
for constructing the generating function of the probability distribution
of R_n; we also establish directly an exact analytic expression for the
step-step correlations and the variance <R_n^2> of the walk. From
the expression of <R_n^2>, which is not straightforward to derive
from the probability distribution, we show that, for n going to infinity,
the variance of any of these walks behaves as n, provided p>0. Moreover,
in many cases, for a very small fixed value of p, the variance exhibits
a crossover phenomenon as n increases from a not too large value. The
crossover takes place for values of n around 1/p. This feature may mimic
the existence of a non-trivial Hurst exponent, and induce a misleading
analysis of numerical data issued from mathematical or natural sciences
experiments.
Click here to download
this paper from xxx archive.
(return to Contents)
Abstract: Lattice models describing the spatial spread of rabies
among foxes are studied. In these models, the fox population
is divided into three-species: susceptible, infected or incubating,
and infectious or rabid. They are based on the fact that susceptible
and incubating foxes are territorial while rabid foxes have lost
their sense of direction and move erratically. Two different models
are investigated: a one-dimensional coupled-map lattice model,
and a two-dimensional automata network model. Both models take into
account the short-range character of the infection process and the
diffusive motion of rabid foxes. Numerical simulations show how the
spatial distribution of rabies, and the speed of propagation of the
epizootic front depend upon the carrying capacity of the environment
and diffusion of rabid foxes out of their territory.
Click here to download
this paper from xxx archive.
(return to Contents)
N. Boccara and H. Fukś,
Number-conserving Cellular Automaton Rules, Fundamenta
Informaticae 52 1-13 (2002)
Abstract: A necessary and sufficient condition for a one-dimensional
q-state n-input cellular automaton rule to be number-conserving
is established. Two different forms of simpler and more visual
representations of these rules are given, and their flow diagrams
are determined. Various examples are presented and applications
to car traffic are indicated. Two nontrivial three-state three-input
self-conjugate rules have been found. They can be used to model
the dynamics of random walkers.
Click here to download
this paper from xxx archive.
(return to Contents)
Abstract: We derive the critical behavior of a CA traffic flow
model using an order parameter breaking the symmetry of the jam-free phase.
Random braking appears to be the symmetry-breaking field conjugate to the
order parameter. For $v_{\max}=2$, we determine the values of the critical
exponents $\beta$, $\gamma$ and $\delta$ using an order-3 cluster approximation
and computer simulations. These critical exponents satisfy a scaling relation,
which can be derived assuming that the order parameter is
a generalized homogeneous function of $|\rho-\rho_c|$ and $p$
in the vicinity of the phase transition point.
Click here to download
this paper from xxx archive.
Click
here to download this paper from IOP Web site.
(return to Contents)
Abstract: We present a probabilistic cellular automaton with two
absorbing states, which can be
considered a natural extension of the Domany-Kinzel
model. Despite its simplicity, it shows
a very rich phase diagram, with two second-order
and one first-order transition lines that
meet at a tricritical point. We study the
phase transitions and the critical behavior of the
model using mean field approximations, direct
numerical simulations and field theory. A
closed form for the dynamics of the kinks
between the two absorbing phases near the
tricritical point is obtained, providing
an exact correspondence between the presence of
conserved quantities and the symmetry of
absorbing states. The second-order critical curves
and the kink critical dynamics are found
to be in the directed percolation and parity
conservation universality classes, respectively.
The first order phase transition is put in
evidence by examining the hysteresis cycle.
We also study the "chaotic" phase, in which two
replicas evolving with the same noise diverge,
using mean field and numerical techniques.
Finally, we show how the shape of the potential
of the field-theoretic formulation of the
problem can be obtained by direct numerical
simulations.
Click here to download
this paper from xxx archive.
(return to Contents)
Abstract: It is shown that a variety of deterministic cellular
automaton models of highway traffic
flow obey a variational principle which
states that, for a given car density, the average car flow
is a non-decreasing function of time. This result is established
for systems whose configurations exhibits local jams of a given
structure. If local jams have a different structure, it is shown
that either the variational principle may still apply to systems
evolving according to some particular rules, or it could apply under
a
weaker form to systems whose asymptotic
average car flow is a well-defined function of car density.
To establish these results it has been necessary to characterize
among all number-conserving cellular automaton rules which
ones may reasonably be considered as acceptable traffic rules. Various
notions such as free-moving phase, perfect and defective tiles,
and local jam play an important role in the discussion. Many illustrative
examples are given.
Click here to download
this paper from xxx archive.
(return to Contents)
(return to Contents)