SCIENTIFIC PROGRAMS AND ACTIVITIES

September  1, 2014

Automata 2007
13th International Workshop on Cellular Automata

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.