Home Call for papers Committees AUTOMATA'10
Programme Registration Venue Contact
Abstracts Tutorials
Conference Schedule

Selected Abstracts

In this page we present some selected abstracts that will be presented in the conference.
Structure and Evolution of the Indian Railway Network
Saptarshi Ghosh, Avishek Banerjee, Naveen Sharma, Sanket Agarwal, Animesh Mukherjee, Niloy Ganguly
The structure and evolution of the transportation networks of a country are primary indicators of its economic progress. In this paper, we study the Indian Railway Network (IRN) as a weighted complex network, with emphasis on its present structure and its evolution over the past two decades. Stations are considered as the nodes in the network, while the weighted edges represent the number of trains linking two stations. Apart from the small-world characteristics and exponential degree distribution of the IRN, we explore the correlations of the amount of traffic with the topology of the network. With respect to the evolution of the IRN, we observe that the IRN is becoming denser with time, following the densification power law; further, the network is found to become more homogeneous with respect to node-degrees over time, which indicates improved connectivity among stations.

InterCell: Large scale cellular and interactive computation
Hervé Frezza-Buet
In the field of neural computation, available parallel simulators are mainly dedicated to spiking neurons (Brette et al., 2007), but very few attempts have been made to design simulators for discrete dynamical systems like cellular automata and other models extended from them. The InterCell project (Frezza-Buet, 2007) addresses this issue, providing a C++ API and related tools to design such systems, hiding the parallelization to the designer.

Local and Regional Interactions for Programming Discrete Models of Complex Systems
Giandomenico Spezzano
This paper describes CARPET-R, a language for cellular programming which extends the cellular automata model through the concept of regions. Regions are spatio-temporal objects that define zones of the automaton (set of cells), containing interesting and meaningful data patterns or trends that can be defined as events. Each cell of the automaton can monitor regions for a given period and observe their evolution by global functions (max, min, sum etc.). Furthermore, each cell can have an associated attribute called its perception rating, that indicates how far that cell can ‘see’. On the basis of this value and the cell’s position in the cellular space, we can define the regions that are visible to the cell. Using these constructs, a cell can define significant events to extract data of interest in one or more regions and perform actions when an event is detected. In the paper, we show that regions simplify programming and allow the building of more complex models. After describing the main constructs of CARPET-R, the paper illustrates the region-based programming model by describing the design of a parallel model of animal migration. Performance results of the model implemented on a Cluster Computer are also given.

Critical mass effect in the contact process of decision making
M. Rybak and K. Kułakowski
Collective actions need often a chain reaction of approving decisions, made by individuals. According to the Granovetter’s theory, such a decision is triggered by some threshold number of agents who joined the action. The effect has been investigated within the so-called critical mass theory. We are going to investigate this effect in social networks in terms of the theory of contact processes. The model parameter is the threshold number of neighbors k* who adopted the collective strategy; a contact with k* individuals is the necessary and sufficient condition for making the approving decision. The process depends of the clustering coefficient C. In trees, where C=0, the process does not spread at all for k*>1. In two-dimensional spatial networks, where C=0.46, the critical connectivity K for k*=2 is about 7.8. Near the critical point, the inverse time of getting the system boundaries varies with the mean degree <k> as (<k>-K)a, with a close to 0.6. Numerical calculations are in progress.

Virtual Stability: A General Principle of Complex Adaptive Systems?
Burton Voorhees
The concept of virtual stability is defined as a state in which a system employs self-monitoring and adaptive control to maintain itself in a configuration that would otherwise be unstable. The extra energy expended in doing this is compensated by the advantage gained in increased behavioral flexibility in the face of random environmental perturbations. A population model is developed as a proof of concept. In the model, transition probabilities between three population types are used to emulate stability: stable types have low probabilities of making transitions to other types, unstable types have high transition probabilities. The model itself consists of two stable types and one unstable type and conditions are explored that lead to dominance by the unstable type. Under certain conditions the unstable type can defeat a stable type, even in an environment that always favors the stable type. Presentation of the model is followed by discussion of the importance for managed stability for complex systems, and the evolutionary advantage the capacity to maintain virtually stable states provides. This leads to the suggestion that such advantage gives an argument both for the directionality of evolution and for the emergence of self-consciousness.

Simulating cancer growth with cellular automata: can it help?
Andreas Deutsch
Deciphering the principles of cancer growth is crucial for the development of new therapy concepts. Besides increasingly complex molecular investigations, mathematical modelling and computer simulation of selected aspects of cancer growth have become popular within the last few years. Here, we focus on the analysis of cancer invasion. Lattice-gas cellular automaton (LGCA) models allow for an adequate description of individual invasive cancer cell behaviour (microscopic level). We will show how approximations of the LGCA models allow for prediction of emerging macroscopic properties (in particular of the invasion speed). Furthermore, we will use our models to derive and test a new cancer invasion hypothesis on the basis of experimental data from in vitro glioma cell invasion assays.

Sparseness in model gene regulatory networks
Marcin Zagórski
Gene regulatory networks typically have low in-degrees, whereby any given gene is regulated by few of the genes in the network. They also tend to have broad distributions for the out-degree. What mechanisms might be responsible for these degree distributions? Starting with an accepted framework of the binding of transcription factors to DNA, we consider a simple model of gene regulatory dynamics. There, we show that selection for a target expression pattern leads to the emergence of minimum connectivities compatible with the selective constraint. As a consequence, these gene networks have low in-degree, and "functionality" is parsimonious, i.e. is concentrated on a sparse number of interactions as measured for instance by their essentiality. Furthermore, we find that mutations of the transcription factors drive the networks to have broad out-degrees. Finally, these classes of models are evolvable, i.e. significantly different genotypes can emerge gradually under mutation-selection balance.

Counting Fixed Point Configurations of Cellular Automata with Simple Threshold Update Rules
Predrag T. Tošić
We study classical cellular automata with linear threshold functions as the node update rules. We restrict those linear threshold functions to the ones that are also symmetric, and hence can capture the mean field effects studied in statistical physics and other models of very large-scale systems; we call such symmetric linear threshold functions simple. The most prominent representatives of simple threshold functions on the Boolean domain are the AND, OR and Majority update rules.
We completely characterize the configuration spaces of simple threshold CA, with a focus on the Majority update rule that results in the most interesting dynamics among the CA in this very restricted class. In particular, we show the combinatorics behind determining the total number of fixed point configurations for simple threshold CA. Even when the combinatorics is non-trivial, such as in the case of Majority update rule, the counting problems of interest (such as determining the exact number of fixed points) are all computationally tractable. This is in stark contrast to our intractability of counting results demonstrated for the related classes of Boolean network or graph automata with similarly restricted node update rules, that are characterized by (seemingly) only slightly more complex structures when it comes to (i) the underlying interconnection topologies (or cellular spaces) and (ii) diversity of the node update rules, i.e., whether all the nodes use the same update rule (as in the classical CA), or two different rules from the given class are allowed. The conclusion is that even most modest generalizations of the classical CA with simple threshold update rules lead to a phase transition from the dynamics that is "easy in principle" to predict and fully characterize, to provably very complex and intractable dynamics.

Modeling Large-Scale Multi-Agent Systems with Sequential and Genuinely Asynchronous Cellular Automata
Predrag T. Tošić
We study certain types of cellular automata (CA) viewed as an abstraction of the large-scale multi-agent systems (MAS). The classical CA model needs to be modified in several important respects, in order to become a relevant and sufficiently general model for the large-scale MAS, and so that thus generalized model can capture many important MAS properties at the level of agent ensembles and their long-term behavior patterns. In this paper, we focus on the issue of inter-agent communication in CA, and propose the sequential cellular automata (SCA) as the first step, and the genuinely asynchronous cellular automata (ACA) as the ultimate deterministic CA-based abstract model for large-scale MAS made of simple reactive agents. We first formulate deterministic and nondeterministic versions of sequential CA, and then we address certain configuration space properties (i.e., possible dynamic behaviors) of a class of sequential threshold CA. In particular, we compare and contrast those properties with the corresponding properties in the classical, parallel (that is, perfectly synchronous) threshold CA. Finally, we outline what would be an appropriate CA-like abstraction for the large-scale distributed computing insofar as the inter-agent communication model is concerned, and in that context we propose genuinely asynchronous CA.

GCA-w Algorithms for Traffic Simulation
Rolf Hoffmann
The GCA-w model (Global Cellular Automata with write access) is an extension of the GCA (Global Cellular Automata) model, which is based on the cellular automata (CA) model. Whereas the CA model uses static links to local neighbors, the GCA model uses dynamic links to potentially global neighbors. The GCA-w model is a further extension that allows modifying the neighbors’ states. Thereby neighbors can dynamically be activated or deactivated. Modeling traffic flow is a good example showing the usefulness of the GCA-w model. The Nagel-Schreckenberg algorithm for traffic simulation is first described as CA and GCA, and then transformed into the GCA-w model. Furthermore, this algorithm is extended, allowing to deactivate and to activate cars stuck in a traffic jam in order to save computation time and energy

FLAME: A Platform for High Performance Computing of Complex Systems
Mesude Bicak
This paper presents FLAME Flexible Large-scale Agent-based Modelling Environment for modelling various real complex systems from biological, economic and sociological systems. FLAME allows models to be automatically parallelised on high performance computing grids enabling large number of agents to be simulated in less time than other comparable simulation frameworks. The framework handles this parallelism itself allowing realistic models to be simulated. Researchers are hindered by complexities of porting models on parallel platforms and time taken to run large simulations on a single machine which FLAME overcomes.
Communication between agents is achieved through the use of messages using MPI to port messages across different machines and platforms. The communication is handled using an intelligent message board library, Libmboard, which allows filtering of messages reducing the work for the agents improving simulation performances. Using a distributed memory model, single program multiple data (SPMD), the framework is able to handle deadlocks through synchronisation points which ensure all data is coordinated among agents. Performance results of simulating 106 agents implemented on a computing grid are also presented.

Study heart rate variability with tools from complex networks
Danuta Makowiec, Joanna Wdowczyk-Szulc, Marta Żarczyńska-Buchowiecka, Rafał Gałaska, Marcin Gruchała, Andrzej Rynkiewicz
Heart rate, measured as beat-to-beat intervals, is not constant but varies in time. It is believed that time intervals between subsequent normal heart contractions carry information about the regulatory system of the heart. How to quantify such signals is not clear and because of that heart rate variability is still apart from the clinic routine. In the following we consider transfering of a heart rate signal into a directed network and then study the signal properties by complex network tools. The signals to study were collected from patients recovering after the heart transplantation. The basic aim is to classify the progress of adapting of the new heart --- graft. Our investigations are preliminary --- any criticisms and advices how to deal with such networks are welcome.

Emergent network structure, epigenetic organization and evolvable robustness in an artificial genome model
Thimo Rohlf
An important contribution to the processing of genetic information comes from transcription factors (TFs) binding to specific DNA sequences, and thereby activating or inhibiting transcription of genes (typically) downstream. Many models of gene regulatory networks (GRNs), however, neglect both the sequence-based nature of TF-gene interactions and the spatial extension of the genome. Here, we study a simple artificial genome model that allows to include these additional levels of information into Boolean GRN models.
We analyze statistical properties of randomly generated genomes both on the sequence- and network level, and show that this model correctly predicts the frequency of genes in genomes as found in experimental data. Distributions of the lengths of non-coding regions, and asymmetries in GRN in- and outdegree distributions, as found in biological data, follow from geometric properties of genomes and constraints on TF sequences.
Using an evolutionary algorithm based on stabilizing selection for a phenotype, we show that dynamical robustness against single base mutations, as well as against random changes in initial states of regulatory dynamics that mimic stochastic fluctuations in environmental conditions, can emerge in parallel. Point mutations at the sequence level have strongly non-linear effects on network wiring, including as well structurally neutral mutations and simultaneous rewiring of multiple connections, which occasionally lead to strong reorganization of the attractor landscape and metastability of evolutionary dynamics.

Embedding Kadanoff’s Scaling Picture into the Triangular Lattice
Dominique Désérable
A topological aspect of the renormalization procedures is tackled from the Kadanoff’s scaling picture which splits the “chessboard” into nested blocks and sub-blocks and we study how to embed a similar scheme onto the triangular lattice. Although this nested scheme is straightforward in the chessboard, it is far from being the case in the “honeycomb”. A background is first proposed to highlight the multiple ways of tiling the plane with prototiles, in the square tessellation as well as in the hexagonal tessellation, and to show how the symmetries of the regular tiling may or may not be stabilized by the prototile. It is shown that there exists a prototile that preserves symmetries in the hexagonal case. In the (dual) triangular lattice, this construction generates an “arrowhead” torus which belongs to the family of hierarchical Cayley graphs.

Highway Traffic Modeling & Simulation by Means of Agents on GCA-w
Bruno N. Di Stefano and Anna T. Lawniczak
A highway traffic model of the Nagel-Schreckenberg type can be seen as made up of a CA (Cellular Automaton) acting as a database where all information about the current state of the model is recorded and a number of vehicles implemented as agents able to interpret all information about all possible situations and able to decide what to do next. The number of actions that a vehicle can take at every time step and their complexity are much higher than what is possible in the traditional Nagel-Schreckenberg model. We describe two implementation improvements over the Nagel-Schreckenberg model:
  1. The replacement of the traditional CA with the “Global Cellular Automata” (GCA) and the “Global Cellular Automata with Write access” (GCA-w) developed by Rolf Hoffmann and his collaborators. This allows for faster execution and for the elimination of some potential conflicts during execution.
  2. The possible replacement of reflexive agents with cognitive agents

We have implemented the first improvement and we will present implementation details. We are currently working at the second improvement and we will describe our work in progress about cognitive agents.

AI Planning and fixed points in asynchronous CA
Joerg Hoffmann and Nazim Fatés
AI Planning is concerned with the selection of actions towards achieving a goal. Research on cellular automata (CA) is concerned with the question how global behaviours arise from local up dating rules relating a cell to its direct neighbours. While these two areas are disparate at first glance, we herein identify a problem that is interesting to both: How to reach a fixed point in an asynchronous CA where cells are updated one-by-one? Considering a particular local updating rule, we encode this problem into PDDL and show that the resulting benchmark is an interesting challenge for AI Planning. For example, our experiments determine that, very atypically, an optimal SAT-based planner outperforms state-of-the-art satisficing heuristic search planners. This points to a severe weakness of current heuristics because, as we prove herein, plans for this problem can always be constructed in time linear in the size of the automaton. Our proof of this starts from a high-level argument and then relies on using a planner for flexible case enumeration within localised parts of the argument. Besides the formal result itself, this establishes a new proof technique for CAs and thus demonstrates that the potential benefit of research crossing the two fields is mutual.

Dynamics of Number of Packet in Transit in Free Flow State of Data Network
Anna T. Lawniczak
We study how the dynamics of number of packets in transit (NPT) is affected by the coupling of a routing type with a volume of incoming packet traffic in a data network model. The NPT is a network performance indicator of an aggregate type that measures in “real time” how many packets are in the network on their routes to their destinations. We conduct our investigation using a time-discrete simulation model that is an abstraction of the Network Layer of the ISO OSI Seven Layer Reference Model. This model focuses on packets and their routing. We consider a static routing and two different types of dynamic routings coupled with different volumes of incoming packet traffic in the network free flow state. Our study shows that the order of the values of the NPT mean value functions depends on the coupling of a routing type with a volume of incoming packet traffic and changes when the volume of incoming packet traffic increases and is closed to the critical source load values, i.e. when it is closed to the phase transition point from the network free flow state to its congested state. This research is joint work with Shengkun Xie and other members of A.T. Lawniczak’s research team.

From Computational Neurosience to Cellular Automata
Nicolas Rougier
I will present some works related to computational neuroscience where we defined the notion of asynchronous evaluation in the context of visual attention modeling. By considering those models as being a generalization of cellular automata, we’ll investigate to what extent this notion of asynchronicity can be translated into the cellular automata theory.

Last Update : May 2010