Contents
(return to Contents)
(return to Contents)
(return to Contents)
N. Boccara, Scaling Properties of a Transformation Defined on Cellular Automaton Rules, J. Phys. A: Math. Gen.22 L393-L396 (1989)
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)
R. Bidaux, N. Boccara, and H. Chaté, Order of the transition versus space dimension in a family of cellular automata, Phys. Rev. A 39 3094-3105 (1989)
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)
N. Boccara and M. Roger, Block Transformations of One-Dimensional Deterministic Class-3 Cellular Automata, J. Phys. A: Math. Gen. 24 1849-1865 (1991)
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)
N. Boccara, J. Nasser and M. Roger, Particlelike Structures and their Interactions in Spatiotemporal Patterns Generated by One-Dimensional Deterministic Cellular-Automaton Rules, Physical Review A 44 (2) 866-875 (1991)
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)
N. Boccara, Transformations of One-Dimensional Cellular Automaton Rules by Translation-Invariant Local Surjective Mappings, Physica D 68 416-426 (1993)
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)
G. Odor, N. Boccara and G. Szabo Phase Pransition Study of a One-Dimensional Probabilistic Site-Exchange Cellular Automaton Phys. Rev. E 48 3168-3171 (1993)
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)
N. Boccara and K. Cheong, Critical Behaviour of a Probabilistic Automata Network SIS Model for the Spread of an Infectious Disease in a Population of Moving Individuals , J.Phys. A: Math. Gen. 26 3707-3717 (1993)
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)
N. Boccara, K. Cheong and M. Oram, Probabilistic Automata Network Epidemic Model with Births and Deaths Exhibiting Cyclic Behaviour, J. Phys. A: Math. Gen. 27 1585-1597 (1994)
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)
N. Boccara, O. Roblin and M. Roger, Route to Chaos for a Global Variable of Two-Dimensional "Game of life type" Automata Network, J. Phys. A: Math. Gen. 27 8039-8047 (1994)
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)
N. Boccara, O. Roblin and M. Roger, An Automata Network Predator-Prey Model with Pursuit and Evasion, Phys. Rev. E 50 4531-4541 (1994)
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)
N. Boccara, H. Fukś and Q. Zeng, Car Accidents and Number of Stopped Cars Due to Road Blockage on a One-lane Highway, J. Phys. A: Math. Gen. 30 3329-3332 (1997)
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)
N. Boccara, Automata Network Models in Ecology and Epidemiology, Lecture presented at the EU Advanced Workshop on Dynamical Modeling in Biotechnology held at Torino (Italy) 27 May-9 June 1996, edited by F. Bagnoli and S. Ruffo (Singapore: World Scientific, 2001)
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)
N. Boccara and H. Fukś, Cellular Automaton Rules Conserving the Number of Active Sites, J. Phys. A: Math. Gen. 31 6007-6018 (1998).
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)
N. Boccara and M. Roger, Totalistic Two-dimensional Cellular Automata Exhibiting Global Periodic Behavior, Int. J. Mod. Phys. C 10 1017-1024 (1999)
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)
R. Bidaux and N. Boccara , Correlated Random Walks with a Finite Memory Range, Int. J. Mod. Phys. C 11 921-947 (2000)
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)
A. Benyoussef, N. Boccara, H. Chakib and H. Ez-Zahraouy, Lattice Three-Species Models of the Spatial Spread of Rabies Among Foxes, Int. J. Mod. Phys. C 10 1025-1038 (1999)
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)
N. Boccara and H. Fukś, Critical Behavior of a Cellular Automaton Highway Traffic Model, J. Phys. A: Math. Gen. 33 3407-3415 (2000)
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)
F. Bagnoli, N. Boccara, and R. Rechtman, Nature of Phase Transitions in a Probabilistic Cellular Automaton with Two Absorbing States, Phys. Rev. E 63 046116-1-9
(2001)
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)
N. Boccara, On the existence of a variational principle for deterministic cellular automaton models of highway traffic flow, Int. J. Mod. Phys. C 12 1-16 (2001)
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-conservingcellular 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)
H. Fukś and N. Boccara, Convergence to equilibrium in a class of interacting particle systems evolving in discrete time, Phys. Rev. E 64 016117-1-6 (2001)
Abstract: We conjecture that for a wide class of interacting particle systems evolving in discrete time, namely conservative cellular automata with piecewise linear flow diagram, relaxation to the limit set follows the same power law at critical points. We further describe the structure of the limit sets of such systems as unions of shifts of finite type. Relaxation to the equilibrium
resembles ballistic annihilation, with ``defects'' propagating in opposite direction annihilating upon collision.
Click here to download this paper from xxx archive.
(return to Contents)
A. Benyoussef, N. Boccara, H. Chakib, and H. Ez-Zahraouy, Traffic Flow in a 1D Cellular Automaton Model with Open Boudaries, Chinese J. Phys. 39 428-440 (2001)
Abstract: We have studied open boundary cellular automaton models for highway one-lane traffic flow using a mean-field approximation and numerical simulations. Our contribution focuses on the influence of the braking probability and the maximum speed. Phase diagrams for different speed limits are presented. The mean-field approximation is in good agreement with numerical simulations.
(return to Contents)
A. Moreira, N. Boccara, and E. Goles, On Conservative and Monotone One-dimensional Cellular Automata and their Particle Representation, Theoretical Computer Science 325 285-316 (2004)
Abstract: Number-conserving (or conservative) cellular automata have been used in several contexts, in particular traffic models, where it is natural to think about them as systems of interacting particles. In this article we consider several issues concerning one-dimensional cellular automata which are conservative, monotone (specially ``non-increasing''), or that allow a weaker kind of conservative dynamics. We introduce a formalism of ``particle automata'', and discuss several properties that they may exhibit, some of which, like anticipation and momentum preservation, happen to be intrinsic to the conservative CA they represent. For monotone CA we give a characterization, and then show that they too are equivalent to the corresponding class of particle automata. Finally, we show how to determine, for a given CA and a given integer b, whether its states admit a b-neighborhood-dependent relabelling whose sum is conserved by the CA iteration; this can be used to uncover conservative principles and particle-like behavior underlying the dynamics of some CA.
Click here to download this paper from xxx archive.
Click here to download this paper from TCS Web site.
(return to Contents)
N. Boccara, Eventually Number-Conserving Cellular Automata, Int. J. Mod. Phys. C 18 35-42 (2007)
Although is undecidable whether a one-dimensional cellular automaton obeys a given conservation law over its limit set, it is however possible to obtain sufficient conditions to be satisfied by a one-dimensional cellular automaton to be eventually number-conserving. We present a preliminary study of two-input one-dimensional cellular automaton rules called \emph{eventually number-conserving cellular automaton rules} whose limit sets, reached after a number of time steps of the order of the cellular automaton size, consist of states having a constant number of active sites. In particular, we show how to find rules having given limit sets satisfying a conservation rule. Viewed as models of systems of interacting particles, these rules obey a kind of Darwinian principle by either annihilating unnecessary particles or creating necessary ones.
Click here to download this paper from xxx archive.
(return to Contents)
N. Boccara and H. Fukś, Motion representation of one-dimensional cellular automaton rules, Int. J. Mod. Phys. C 17 1605-1611 (2006)
Abstract: Generalizing the motion representation we introduced for number-conserving rules, we give a systematic way to construct a generalized motion representation valid for non-conservative rules using the expression of the current, which appears in the discrete version of the continuity equation, completed by the discrete analogue of the source term. This new representation is general, but not unique, and can be used to represent, in a more visual way, any one-dimensional cellular automaton rule. A few illustrative examples are presented.
Click here to download this paper from xxx archive.
Click here to download this paper from the journal site.
(return to Contents)
N. Boccara, Is it possible to control the spread of a globalized culture? Journal of Cellular Automata 2 111-120 (2007)
Abstract: We study a model describing the spread of a globalized culture in a population of individuals localized at the nodes of a social network. The influence of this globalized culture, assumed to be foreign to the local culture, is measured by a probability to convince each individual to adopt its cultural traits. This probability depends upon the degree s---a real between 0 and 1---of ``wise'' skepticism characterizing the personality of each individual and a parameter $a$ representing the resistance of the society as a whole to the spread of the foreign cultural traits. A greater $a$ indicates a stronger resistance of the local culture to globalization. On the other hand, each individual interacts with a random number of other individuals---her cultural neighborhood---uniformly distributed between 1 and a maximum value. The probability distribution of an individual to belong to the cultural neighborhood of another individual has a power-law behavior. A small fraction r of the total population belonging to the tail of this probability distribution have an s-value equal to 1. They represent the most conservative individuals firmly attached to their local culture.
(return to Contents)
N. Boccara, Randomized Cellular Automata Int. J. Mod. Phys. C 18 1303-1312 (2007)
Abstract: We define and study a few properties of a class of random automata networks. While regular finite one-dimensional cellular automata are defined on periodic lattices, these automata networks, called randomized cellular automata, are defined on random directed graphs with constant out-degrees and evolve according to cellular automaton rules. For some families of rules, a few typical a priori unexpected results are presented.
Click here to download this paper from the journal site.
(return to Contents)
N. Boccara, Models of Opinion Formation: Influence of Opinion Leaders Int. J. Mod. Phys. C 19 93-109 (2008)
Abstract: This paper studies the evolution of the distribution of opinions in a population of individuals in which there exist two distinct subgroups of highly-committed, well-connected opinion leaders endowed with a strong convincing power. Each individual, located at a vertex of a directed graph, is characterized by her name, the list of people she is interacting with, her level of awareness, and her opinion. Various temporal evolutions according to different local rules are compared in order to find under which conditions the formation of strongly polarized subgroups, each adopting the opinion of one of the two groups of opinion leaders, is favored.
(return to Contents)
N. Boccara, Phase Transitions in Cellular Automata To appear in the Encyclopedia of Complexity, Springer-Verlag
Article Outline: Glossary I. Definition of the Subject,
II. Introduction, III. The Domany--Kinzel Cellular Automaton, IV. Car
Traffic Models,
V. Epidemic Models, VI. &Future Directions, References, Books and
Reviews
(return to Contents)
N. Boccara, Maintenance and Disappearance of Minority Languages: A Cellular Automaton Model, to appear in Journal of Cellular Automata
Abstract: This paper presents and studies a cellular automaton model of the evolution of the language spoken either by groups of immigrants who take permanent residence in a country in which the language spoken by the natives is different from their own or by Aboriginal people whose country has been invaded by a group of individuals imposing their language and culture in order to determine which factors help maintaining the minority language.
(return to Contents)
N. Boccara, A Cellular Automaton Modeling the Struggle to Control the Media, Int. J. Mod. Phys. C 20 1-14 (2009)
Abstract: A free and fair press is an essential condition for democracy. In many western countries the media production, distribution, ownership, and funding is dominated by corporations, and therefore governed by the idea of maximizing profits for the investors making freedom and fairness of the press very questionable. There exist, however, a number of political activists who, by writing books and articles and giving talks, are fighting to free the media from the influence of big corporations. In this paper we present a simple cellular automaton model of this struggle.
(return to Contents)
N. Boccara, Voters' Fickleness: A Mathematical Model, submitted
Abstract: This paper presents a spatial agent-based model in order to study the evolution of voters' choice during the campaign of a two-candidate election. Each agent, represented by a point inside a two-dimensional square, is under the influence of its neighboring agents, located at a Euclidean distance less than or equal to $d$, and under the equal influence of both candidates seeking to win its support. Moreover, each agent located at time $t$ at a given point moves at the next time step to a randomly selected neighboring location distributed normally around its position at time $t$. Besides their location in space, agents are characterized by their level of awareness, a real $a\in [0,1]$, and their opinion
$\omega\in \{-1, 0, 1\}$, where -1 and +1 represent the respective intentions to cast a ballot in favor of one of the two candidates while 0 indicates either disinterest or refusal to vote. The essential purpose of the paper is qualitative; its aim is to show that voters' fickleness is strongly correlated to the level of voters' awareness and the efficiency of candidates propaganda.
(return to Contents)