August 27-29, 2007
The Fields Institute
Inappropriate Use of the Shoulder in Highways Impact over
the Increase of Gas Consumption
by
Angel Aponte
Universidad Católica Andrés Bello. Av. Teheran, Urb.
Moltanban. La Vega Apartado 20332. Caracas, DC, Venezuela
Coauthors: Saúl Buitrago and José Alí Moreno
A simulation study to quantify a Gas Consumption Increase Fraction
(GCIF), in order to evaluate the impact that over the increase of
gas consumption has an illegal/inappropriate use of the Hard Shoulder
in the highways, is presented. Traffic dynamic in a rectilinear
sector of a two-lane (and Shoulder) highway is modeled and simulated
using an Emergent Microscopic Model Based on a Cellular Automaton
(EMMBCA). The EMMBCA is an extension of the original one-lane Nagel-Schreckenberg
model for identical vehicles, which incorporate lane change maneuvers
and additional features that take into account some aspects related
with drivers’ behavior. The proposed GCIF is estimated calculating
the inverse of the area under the graph of the Fundamental Diagram
Flow vs. Density. It is suggested that, under certain conditions,
the inappropriate use of the Shoulder is related with the increase
of appearance of traffic jams. The GCIF quantifies this increase,
obtaining values as great as 30conditions considered, if Hard Shoulder
is used as another circulation lane, 30
--------------------------------------------------------------------------------
Surjectivity and surjunctivity of cellular automata in Besicovitch
topology
by
Silvio Capobianco
School of Computer Science, Reykjavik University
Introduced in the context of cellular automata by E. Formenti and
others [3], the Besicovitch pseudodistance measures the density
of the set where two configurations differ. The quotient space obtained
by identifying configurations at distance zero, endowed with the
induced metric, usually has topological properties different than
those of the space of configurations. However, provided that certain
conditions are satisfied, cellular automata induce transformations
of the Besicovitch space that are continuous in the Besicovitch
topology.
We extend a result of Blanchard, Formenti and Kurka [1] and show
that, under suitable hypotheses --- which are satisfied by the d-dimensional
space and the Moore (or von Neumann) neighborhoods, but also in
more complex environments [2] --- a cellular automaton is surjective
if and only if the induced transformation in the Besicovitch space
is surjective. We then show that, under the same hypotheses, if
the induced transformation is injective, then it is also surjective:
this mirrors a well known property of cellular automata in the usual
product topology [4,5].
References:
[1] F. Blanchard, E. Formenti, P. Kurka, Cellular automata in Cantor,
Besicovitch, and Weyl topological spaces, Complex Systems 11(2)
(1999), 107-123.
[2] T.G. Ceccherini-Silberstein, A. Machi', F. Scarabotti, Amenable
groups and cellular automata, Ann. Inst. Fourier, Grenoble 42 (1999),
673-685.
[3] G. Cattaneo, E. Formenti, L. Margara, J. Mazoyer, A shift-invariant
metric on S^Z inducing a non-trivial topology, Lect. Not. Comp.
Sci. 1295 (1997), 179-188.
[4] E.F. Moore, Machine models of self-reproduction, Proc. Symp.
Appl. Math. 14 (1962), 17-33.
[5] J. Myhill, The converse of Moore's Garden-of-Eden theorem,
Proc. Am. Math. Soc. 14 (1962), 685-686.
--------------------------------------------------------------------------------
A Cellular Automata Model of the Spread of HIV in a Community
of Injection Drug Users
by
Vahid Dabbaghian-Abdoly
Complex Systems Modelling Group, The IRMACS Centre, Simon Fraser
University, British Columbia, Canada
Coauthors: Natasha Richardson (nmr@sfu.ca), Alexander Rutherford
(sandyr@irmacs.sfu.ca)
Within a health promotion and harm reduction framework, modelling
the spread of Human Immunodeficiency Virus (HIV) among Injection
Drug Users (IDU) is a priority issue. In this poster we present
a Cellular Automata model which describes the dynamics of HIV based
on hypothetical social interactions between members of an IDU community.
In particular we apply this model to a large scale urban environment
and we show the results of the implementations of this model on
the computer algebra system Maple.
--------------------------------------------------------------------------------
Can the spatially extended populations replicate the logistic
map?
by
Witold Dzwinel
agh university of science and technology, dept. of computer science,
al. mickiewicza 30, 30-059 krakow, poland
The spatial distribution of individuals and the way they interact
with their local neighborhood are the two fundamental factors, which
are neglected in simplistic ecological paradigms such as the logistic
law. Therefore, there is no curiosity in that it can fail in describing
the time evolution of many organisms. More provoking is the reverse
problem. Can a spatially extended population reproduce the logistic
map? If it can, what conditions must it satisfy? Existing spatial
logistic models address these questions only partially, focusing
only on the steady-state population dynamics [1]. Meanwhile, in
many cases the pre-chaotic and chaotic modes decide about the qualitative
changes in population dynamics [2,3]. We attack the problem within
the formalism of a certain class of stochastic 2-D cellular automata
assuming intense mobility of individuals. Their motion can compensate
the influence of the spatial degrees of freedom on the population
growth. Then the CA rule defining microscopic interactions remains
the only factor, which determines the temporal dynamics of the whole
colony. We derive the class of microscopic rules for which the global
dynamics of the spatially extended CA population matches exactly
the logistic map. However, for the motionless populations, only
in the cases of extreme large dispersal and competition it is possible
to reproduce the global chaotic behavior properly. Otherwise, the
spatial patterns emerge, which can represent a kind of self-preservation
mechanism. It allows the population for avoiding advert effects
of chaos and guarantees the steady-state evolution.
Keywords: logistic map, spatially extended systems, cellular automata,
patterns, chaos
References
1. Law, R., Murrell, D.J., Dieckmann, U., (2003). Population Growth
in Space and Time. Spatial Logistic Equation, Ecology, 84 (1), 252-262.
2. Kendall, B.E., (1998). Spatial Structure, Environmental Heterogeneity,
and Population Dynamics: Analysis of the Coupled Logistic Map, Theor.
Popul. Biol., 54, 11-37.
3. Lloyd, A.L., (1995). The Coupled Logistic Map. A Simple Model
for the Effects of Spatial Heterogeneity on Population Dynamics,
J. theor. biol. 173, 213-230
--------------------------------------------------------------------------------
Non-Locality and Multiple Populations - Variants of the Game
of Life
by
Kent Fenwick
School of Computing, Queen's University, Kingston, Ontario, Canada
Coauthors: Sina Dengler, Selim Akl
We introduce variants of the Game of Life cellular automaton. While
the Game of Life is an excellent example of emergence it fails to
capture basic life conditions due to its limited single population,
locally based rules. The first variation attempts to model more
complex situations of everyday life by exploring friend and foe
models and the effect of non-local rules on a population's growth
and survival. For example, what if your neighbours do not want you
to survive, or what if you have powerful friends in far away places.
The second simulation attempts to model the complex behaviors of
single and multiple populations using well defined mathematical
models of population growth. Models such as the Malthusian scheme
for population growth and the Lotka-Volterra model for interacting
populations are simulated on Conway's life board. In both cases
we find the variants create rich simulations based on rules found
in real life and nature.
--------------------------------------------------------------------------------
Cellular Automata and Dynamic Monopolies
by
Paola Flocchini
School of Information Technology and Engineering, University of
Ottawa
Let G be a graph where to each node it is associated a boolean
state (black or white). The graph evolves in discrete time steps
and at each step the state of a node changes according to the majority
of the states of the neighbouring nodes. Depending on the initial
configuration of states, and on the definition of majority, different
dynamics could occur.
An initial configuration that leads the system to a mono-cromatic
fixed point is called dynamo. Dynamos are particularly interesting
in distributed computing and communication networks because they
describe the propagation of faults in majority-based systems. The
research focus is on the size and characteristics of the smallest
possible dynamo for a given graph (i.e., smallest configuration
of faults that would disrupt the system).
In this talk I will survey some recent results in these areas.
--------------------------------------------------------------------------------
Preimage trees in cellular automata
by
Henryk Fuks
Brock University
Given cellular automaton rule and a string of symbols, one can
construct a set of its preimages of that string under the CA rule.
For each of these preimages, one can compute a set of further preimages,
and one can repeat this procedure iteratively, producing a graph
that we call a preimage tree. For many elementary cellular automata
rules preimage trees exhibit interesting regularities, which can
be explored by a variety of combinatorial methods, such as generating
functions. We will show how to use these regularities to compute
probabilities of occurrence of symbols and blocks of symbols in
states evolving from random initial conditions.
--------------------------------------------------------------------------------
Parallel and Serial Dynamics in Boolean Networks
by
Eric Goles
Universidad Adolfo Ibañez, Diagonal las Torres 2640, Peñalolen-
Santiago- Chile
Coauthors: Lilian Salinas Universidad de Concepción, Chile
I will present some results concerning the attractors of boolean
networks ( fixed points and
periodic configurations) under differents iterations modes. In
particular, for the parallel and
the serial update, I will prove under reasonable conditions that
the serial and the parallel
iterations have only differents cycles. To do that I will use the
properties of the interconnection
graph associated to the boolean network.
--------------------------------------------------------------------------------
Lattice-gas cellular automata as microscopic models of cell
migration in heterogeneous environments
by
Haralambos Hatzikirou
TU Dresden
Coauthors: A. Deutsch
Understanding the precise interplay of moving cells with their
typically heterogeneous environment is crucial for central biological
processes as embryonic morphogenesis, wound healing, immune reactions
or tumor growth. Mathematical models allow for the analysis of cell
migration strategies involving complex feedback mechanisms between
the cells and their microenvironment. Here, we introduce a cellular
automaton (especially lattice-gas cellular automaton-LGCA) as a
microscopic model of cell migration together with a (mathematical)
tensor characterization of different biological environments. Furthermore,
we show how mathematical analysis of the LGCA model can yield an
estimate for the cell dispersion speed within a given environment.
--------------------------------------------------------------------------------
Space-time directional Lyapunov exponents for cellular automata
by
Brunon Kaminski
Nicolaus Copernicus University, Poland
Coauthors: Maurice Courbage (Universite Paris VII)
Let X be the set of all double infinite sequences (configurations)
with values in a finite alphabet equipped with the shift transformation
s , a cellular automaton transformation f and a Borel probability
measure m invariant with respect to s and f.
In order to account of the space-time complexity of cellular automata
Milnor ([2]) introduced a generalization of the dynamical entropy
which he called the directional entropy.
Lyapunov exponents in the theory of cellular automata have been
introduced first by Wolfram ([4]). The idea was to find a characteristic
quantity of the instability of the dynamics of cellular automata
analogous to the Lyapunov exponents which measure the instability
of the orbits of ergodic differentiable dynamical systems under
perturbations of initial conditions. A first rigorous mathematical
definition of these exponents has been given by Shereshevsky ([3])
in the framework of ergodic theory.
In a joint paper with Courbage ([1]) we introduce the notion of
space-time directional Lyapunov exponents lv+, lv- , v ? R×R+.
We define them as the averages along a given space-time direction
v ? R×R+ of the speed of propagation to the left (resp. right)
of a front of right (resp. left) perturbations of a given configuration
x ? X.
We prove that the mappings v?lv+, lv- are positively homogeneous,
continuous and are related to the directional entropy hv(F) of the
action F of the semigroup Z×Z+ generated by s and f as follows
hv(F) = ?Xhm(s, x)(lv+(x) +lv-(x))m(dx)
where hm(s, x) is the Brin-Katok local entropy of s w.r. to m at
x ? X.
It appears that this inequality becomes an equality for permutative
f and vectors v running over some cones determined by f. Applying
f defined by Coven one can show that in general the above inequality
is not an equality.
References
[1] M. Courbage, B. Kaminski, Space-time directional Lyapunov exponents
for cellular automata, J. Stat. Phys. 124 (2006), 1499-1509.
[2] J. Milnor, On the entropy geometry of cellular automata, Complex
Syst. 2 (1988), 357-386.
[3] M. A. Shereshevsky, Lyapunov exponents for one-dimensional automata,
J. Nonlinear Sci. 2 (1992), 1-8.
[4] S. Wolfram, Cellular Automata and Complexity, Addison-Wesley
P.C. 1994.
--------------------------------------------------------------------------------
Ensemble averageability in network spectra: complex yet similar
networks
by
Dong-Hee Kim
Department of Physics and Astronomy, Northwestern University
Coauthors: Adilson E. Motter
The extreme eigenvalues of connectivity matrices govern the influence
of the network structure on a number of network dynamical processes.
A fundamental open question is whether the eigenvalues of large
networks are well represented by ensemble averages. Here we investigate
this question explicitly and validate the concept of ensemble averageability
in random scale-free networks by showing that the ensemble distributions
of extreme eigenvalues converge to peaked distributions as the system
size increases. We discuss the significance of this result using
synchronization and epidemic spreading as example processes.
--------------------------------------------------------------------------------
Order Independence in Asynchronous Cellular Automata
by
Matthew Macauley
University of California, Santa Barbara
Coauthors: Jon McCammond (University of California, Santa Barbara)
Henning Mortveit (Virginia Tech)
A sequential dynamical system (SDS) consists of an undirected graph
Y, a sequence of vertex functions FY, and a word w over the vertex
set. This talk will be focused on a special case of these systems,
namely, when Y is a circular graph and the local functions are Wolfram
rules. These systems are called asynchronous elementary cellular
automata (ACAs). An ACA is said to be w-independent if its set of
periodic points are independent of the update order. A surprising
result is that for all n > 3, exactly 104 of the 256 Wolfram
rules give rise to w-independent ACAs. The techniques used to prove
this provide good insight into the dynamics of these systems and
the properties of the functions. We will also discuss the 104 rules
and reveal some hidden structure that relates them. Some of these
results can be generalized to general graph dynamical systems, and
they form a natural starting point for the study of stochastic sequential
dynamical systems.
--------------------------------------------------------------------------------
Computational implementation of De Bruijn networks and the
calculus of preimages in several steps for one-dimensional cellular
automata.
by
Juan Carlos Seck Tuoh Mora
Centro de Investigación Avanzada en Ingeniería Industrial,
Universidad Autónoma del Estado de Hidalgo. Carr. Pachuca-Tulancingo
Km. 4.5 Pachuca 42184 Hidalgo, México
Coauthors: Manuel González Hernández Genaro Juárez
Martínez Harold V. McIntosh
De Bruijn diagrams, de Bruijn networks and their matrix representations
have been widely used for calculating preimages for a given configuration
in one-dimensional cellular automata. However up to now most of
these results have been applied for obtaining one-step preimages,
using iterations of the same process whether more backwards steps
are desired. In this work we explain the construction and application
of the Bruijn networks whose paths represent preimages in several
generations. With this implementation we can both enumerate all
the ancestors for a given initial condition and detect long-term
Garden-of-Eden configurations. Some examples are presented in the
search of ancestors for large triangles in Rule 110.
--------------------------------------------------------------------------------
Towards a Basis for Parallel Language Recognition by Cellular
Automata
by
Katsuhiko Nakamura
Tokyo Denki University
Since cellular automata (CA) provide theoretical models for parallel
computation, the CA would replace the classical serial accepters
as the model of language recognition not only in research but also
in future education of formal language and automata theory. The
major obstacle to such development of the CA theory is that several
fundamental problems remain open, since Smith III first introduced
parallel language recognition by one-dimensional CA more than three
decades ago. The author recently showed a language that is recognizable
by CA in linear time but is not recognizable in real time, and proved
that the class of languages recognizable in real time is not closed
under reversal and under concatenation ("Languages not recognizable
in real time by one-dimensional cellular automata, " Jour.
of Computer and System Sciences, in press). These are solutions
to the open problems.
This paper further investigates parallel language recognition power,
especially limitations of the recognition power, of one-way and
two-way CA. Among the subjects on real-time and linear-time recognition
by CA, the paper focuses on parallel recognition of cyclic strings
and recognition by prefix computation, in which each prefix of the
input string is accepted, if the prefix is a member of the language.
The prefix computation is strictly uniform, whereas most parallel
recognition by two-way CA depends on a specific base point such
as the boundary. The paper also lists the important open problems
and poses new problems on the parallel language recognition.
--------------------------------------------------------------------------------
Fix a Local Function and Change Neighborhoods
by
Hidenosuke Nishio
ex. Kyoto University
We introduce a new definition of CA: (S, Q, fn, n), where S is
the cellular space, Q is the set of states, fn is the n-variable
local function and n: {0, 1, ..., n-1}? S is an injection called
neighborhood function, which provides a connection between the n
variables of fn and the n neighbors of a cell. Thus image(n) is
the neighborhood of size n of CA in the ordinary sense.
First we prove the following basic theorems arising from the new
definition.
Theorem 1. By changing the neighborhood function n, infinitely many
different global CA maps are induced by any single local function
fn which is not constant.
Theorem 2. Two CA are called equivalent if their global maps are
equal. Then, the equivalence problem of CA is decidable.
Next we show that reversibility of 2 states 3 neighbors CA is preserved
from changing the neighborhood, but that of 3 states CA is not.
In this context, 1-dimensional reversible ECA appearing in [4] are
re-examined.
This paper is a successor to [1], [2] and [3], but will contain
more results of a Java Applet simulator and a reversibility tester
of 1-dimensional CA, which have been programmed by students from
the University of Karlsruhe. The simulator works for arbitrary local
function, number of states, neighborhood and initial configuration
(including random configurations) up to 1, 000 cells with cyclic
boundary and 1, 000 time steps. The reversibility tester can test
injectivity and/or surjectivity for all permutations of any neighborhood.
Both programs are the first of this kind - arbitrary neighborhoods.
Some unsolved problems and conjectures will be pointed out. Typically,
can Rule 110 be computation universal even when the neighborhood
is different from the standard one {-1, 0, 1}. Is there any other
binary states 3-variables local function, which does not induce
a universal CA for {-1, 0, 1} but does if the neighborhood is different
from {-1, 0, 1}?
[1] Nishio, H.: How does the neighborhood affect the global behavior
of cellular automata? Proceedings of ACRI2006, LNCS 4173, pp. 122-130
(2006) .
[2] Nishio, H. and Worsch, T. : Neighborhood Function for CA, RIMS,
Kyoto University, kokyuroku vol.1554, pp. 16-23 (May, 2007).
[3] Nishio, H.: Changing the Neighborhood of Cellular Automata,
to appear in Proceedings of MCU2007, LNCS 4664, pp. 255-266 (2007).
[4] Wolfram, S.: A New Kind of Science Wolfram Media, Inc. (2002)
--------------------------------------------------------------------------------
Applications of finite automata which simulate behavior of
cellular automata
by
Masaya Nohmi
Kyushu Institute of Technology, Japan
In the 1970s, Prof. Nishio and Prof. Kobuchi proposed finite automata
which simulate behavior of cellular automata. In this talk, some
applications of the finite automata are mentioned.
--------------------------------------------------------------------------------
Spreading Rate of Elementary Cellular Automaton of Rule 40
in Wolfram Class I
by
Fumio Ohi
Nagoya Institute of Technology, JAPAN
For the elementary cellular automaton of rule 40, S. Wolfram has
shown that the time development of any randomly given initial configuration
eventually goes to the 0-configuration, and then rule 40 is classified
into the class I.
On the other hand, a rigorous examination of rule 40 shows us some
unexpected properties of rule 40.
It has already been proved that the discrete dynamical system defined
by rule 40 is the left-shift dynamics and Devanay chaos on the class
of the configurations composed of the two blocks 01 and 011, and
in this article, performing an exact calculation, we show the following
proposition.
For any given real number a between 1/2 and 1, there exists a configuration
in the class of which spreading rate is equal to the real number
a.
This proposition is proved by letting the dynamical system correspond
to an interval dynamical system and using the Ergodic theorem.
The spreading rate and Lyapunov exponent of rule 40 are coincident
on the class of the configuration, and then the theorem is also
true for Lyapunov exponent.
--------------------------------------------------------------------------------
Quantum Cellular Automata
by
Carlos A. Perez-Delgado
University of Waterloo
Coauthors: Donny Cheung
We present a new construction for a quantum mechanical model of
cellular automata (CA). This new model provides a version of CA
which is consistent with the laws of physics as we know them, and
overcomes a number of issues inherent in previously developed models.
Our approach begins by defining a physically sound model of CA,
which separates the traditional transition function into a separate
"read" component and a single-cell "update"
component. This allows us to construct CA based on operators which
commute with lattice translations and avoid potential concurrency
issues arising from the underlying physical system being modelled.
We then generalize the cellular lattice and the "read"
and "update" rules into versions which are consistent
with quantum mechanics. In particular, the states of each lattice
cell becomes a quantum state space, and the "read" and
"update" operators become unitary linear operators over
the quantum system of a local neighbourhood and a single cell, respectively.
We discuss how this new formalism ensures that CA within this model
correspond to well-defined discrete quantum physical systems evolving
in a time- and space-homogeneous manner. We note that this is not
the case for previous models of CA. Finally, our formalism is shown
to be an appropriate abstraction for space-homogeneous quantum phenomena
such as quantum lattice gases, spin chains and others.
--------------------------------------------------------------------------------
Using Chemical Cellular Automata in Simulation of Chemical
Materials
by
Mohammad Hossein Peyravi
Islamic Azad University
Coauthors: Pooya Khosraviyan Dehkordi
In this paper, we use chemical cellular automata as a new tool
to simulation as well as produce of chemical materials such as polymers
and analyzing their stability. For this purpose, first we examine
the cellular automata and the relevant chemical elements characteristics
and then we consider each element as a cell of the cellular automata
and finally for designing its cellular automata, we will draw the
table of rules related to each experiment and then implement an
example to gain a better understanding of the subject.
--------------------------------------------------------------------------------
In the Queue theory, Cellular Automata is a Jackson Model
by
Mohammad Hossein Peyravi
Islamic Azad University
Coauthors: Dr Alizade , Pooya Khosraviyan dehkordi
In this article first we define stochastic processes and queue
models such as D/D/1, M/M/1 and Jackson model. Then by considering
these models we examine cellular automata and shows that cellular
automaton is a Jackson model. Then we use Jackson model formula
such as average number in system, average length of queue, average
waiting time in queue and average total waiting time in system for
cellular automata.
--------------------------------------------------------------------------------
Classifying cellular automata by automorphisms of transition
diagrams
by
Edward Powley
Department of Computer Science, University of York, UK
Coauthors: Susan Stepney (University of York)
We can define a ``symmetry'' of a CA as a bijection on the set
of configurations which commutes with the CA's global update function.
A translation of all cells by a constant offset is a symmetry for
every CA; other examples for particular CAs may include reflections,
rotations, and permutations of the state set.
It can be shown that the group of symmetries for a given CA is isomorphic
to the group of graph automorphisms for that CA's transition diagram.
This gives us a way to study the symmetries; in particular, we can
easily count them by iterating over the structure of the transition
diagram.
Investigation of the elementary CAs suggests a link between the
number of symmetries for a given CA and the complexity of that CA's
dynamics: ``more complex'' CAs generally admit fewer symmetries,
and some ``chaotic'' CAs (e.g. elementary rule 30) have almost no
symmetries other than translations. This suggests that numbers of
symmetries may form the basis of a formal classification scheme
for CAs.
--------------------------------------------------------------------------------
Efficient Divide-and-Conquer Simulations Of Symmetric FSAs
by
David Pritchard
University of Waterloo
A finite-state automaton (FSA) is an abstract machine with finite
working memory, whose input is a string from a finite alphabet,
which reads the input one character at a time, and which has a deterministic
transition function. An FSA is symmetric if its output is independent
of the order in which the input symbols are read, i.e., if the output
is invariant under permutations of the input. We show that, given
a symmetric FSA A, there is a deterministic divide-and-conquer process
that simulates A whose intermediate results are no larger than the
size of A's memory. In comparison, for a general (not necessarily
symmetric) FSA, a similar divide-and-conquer implementation has
long been known via functional composition but entails an exponential
increase in the size of the state space. Our result has applications
to parallel processing and to symmetric FSA networks.
The first step in the construction is to remove some redundancy
in the states of the FSA. The second step is that, assuming the
FSA is irredundant, to show that the black-box property of being
symmetric implies a more ``transparent" property: namely, the
transition operators of the FSA commute. Following the proof of
this result we give the simple construction and discuss possible
extensions.
These results are available as a 7-page preprint on the arXiv,
http://arxiv.org/abs/0708.0580
--------------------------------------------------------------------------------
Linear cellular automata over vector space and their applications
to mathematics and physics.
by
Tadakazu Sato
Toyo University
We consider the matrix theory from the viewpoint of cellular automata.
A matrix can be regarded as a cellular automaton with no local
interaction. We generalize it so that it has local interaction
by using
the theory of linear cellular automata, and apply it to mathematics
(matrix theory, Lie group, Lie algebra, and tensor) and physics
(electromagnetic field
and Lorenz transformation over complex number field)
--------------------------------------------------------------------------------
Classification and Complexity
by
Klaus Sutner
Carnegie Mellon University
The classification of cellular automata often leads to decision
problems that are undecidable or computationally hard in lower comoplexity
classes. We give an overview of the state of affairs and discuss
a number of open problems in the general case and for the subclass
of additive cellular automata.
--------------------------------------------------------------------------------
Towards a framework for high-level manual programming of
cellular automata
by
Sami Torbey
Queen's University, Canada
Coauthors: Selim Akl (Queen's University, Canada)
The ability to obtain complex global behaviour from simple local
rules makes cellular automata an interesting platform for massively
parallel computation. However, manually designing a cellular automaton
to perform a given computation can be extremely tedious, and automated
design techniques such as genetic programming have their limitations
because of the absence of human intuition. In this presentation,
we propose elements of a framework whose goal is to make the manual
synthesis of cellular automata rules exhibiting desired global characteristics
more programmer-friendly, while maintaining the simplicity of local
processing elements. We also demonstrate the power of that framework
by using it to provide intuitive yet effective solutions to the
two-dimensional majority classification problem and the convex hull
of disconnected points problem.
--------------------------------------------------------------------------------
A Cellular Automata Model of Runoff and Infiltration
by
Gilles Valette
CReSTIC SIC, University of Reims, France
Coauthors: Stéphanie Prévost (CReSTIC SIC, University
of Reims, France) Laurent Lucas (CReSTIC SIC, University of Reims,
France) Joël Léonard (Laboratoire d'Agronomie INRA de
Laon-Reims-Mons, France)
We attempt to model and visualize the evolution of the surface
structure of a cultivated soil surface during a rainfall. Our model
is based on a three dimensional Extended Cellular Automaton, which
typically represents a patch of soil of 50cm x 50cm x 10cm, divided
into 2mm side cubic cells. The CA principle permits to obtain an
open simulator which facilitates the integration of different knowledges
coming from the soil science and concerning the processes we have
to simulate. Among these simulated processes, runoff and infiltration
are of high relevance as they drive the evolution of soil surface
structure. We will present our model of soil and the rules we use
for both these processes. These rules are based on simple interpretations
of equations from soil physics and hydrology and permit to obtain
results that are realistic and compare well with those produced
by physical models. We will also show how the CA model is simpler
to understand than others, allthough it is based on the same laws,
such as mass conservation and movement equation.
--------------------------------------------------------------------------------
How to achieve universality in a CA using the same local
rule but different neighborhoods
by
Thomas Worsch
Univ. of Karlsruhe, Germany
Coauthors: Hidenosuke Nishio (Kyoto)
Assume that a number of CA Ci with the same set of states Q but
different local rules and/or different neighborhoods are given.
We are looking for a CA C' with a set of states Q' and a local rule
f':Q'n? Q', and an encoding of CA configurations over Q into CA
configurations over Q' which is independent of the number i identifying
the CA to be simulated, such that the following holds:
For each i there is a neighborhood N'i of size n, such that C'
simulates Ci if it uses f' with neighborhood N'i.
We first show how an arbitrary finite number of CA with different
local rules/neighborhoods can be simulated that way.
Using another encoding of configurations one can even achieve universality
this way.
The technical differences of the encodings used give rise to further
questions for research.
--------------------------------------------------------------------------------
Statistical Analysis of Behaviour of Packets in Transit in
Data Communication Network Model
by
Shengkun Xie
Dept. of Mathematics and Statistics, University of Guelph, Ont N1G
2W1, Canada
Coauthors: Anna T. Lawniczak, Dept. of Math. & Stat., Univ.
of Guelph Pietro Lio, Computer Laboratory, Univ. of Cambridge, Cambridge,
UK Jiaying Xu, while at Dept. of Math. & Stat., Univ. of Guelph
The behaviour of packets in transit in data communication networks
of packet switching type can be complex and often it is difficult
to predict, because it is affected by many variables like network
connection topology, routing algorithms, network’s size or
users’ behaviour. However, for control of flow and congestion
or design of future networks it is important to improve the understanding
of packets in transit behaviour. Using the model of packet switching
networks of automaton on network type we study statistical properties
of packets in transit behaviour. We focus our study on the loads
of incoming traffic near phase transition point from free flow to
congestion. We investigate how statistical properties of packets
in transit behaviour are affected by routing algorithms and network
connection topology. We consider static and adaptive routings. We
present selected results and outline future work.
--------------------------------------------------------------------------------
Emulating Substitution Shifts using Cellular Automata
by
Reem Yassawi
Department of Mathematics, Trent University
Coauthors: Marcus Pivato (Trent University)
Given an alphabet A, A substitution is a mapping t which maps letters
in a finite alphabet A to words (finite sequences) from A. t can
be extended to a mapping on AZ by concatenation, and the subshift
Xt generated by t is the subshift associated to the language of
t. A substitution is primitive if there is a k ? N such that for
all a, b ? A, b appears in tk(a). Given a primitive substitution,
we show that there exist cellular automata which have subsystems
that are isomorphic to (Xt, s) where s is the shift map.
--------------------------------------------------------------------------------
New extensions to some firing squad synchronization solutions
by
Jean-Baptiste Yunès
LIAFA - Université Paris Diderot, 175 rue du chevaleret,
75013 Paris
We will show that it is possible to extend existing implementations
of many solutions to the linear firing squad synchronization problem
such that they can be used to synchronize whatever is the state
used to initiate the process or such that the initiator cell is
able to be located anywhere on the line. The noticeable and surprising
thing is that these extensions can be made by simple addition of
new rules to the transition function without modifying the set of
states.
