JAC 2010

Journées Automates Cellulaires

Turku, Finland, December 15-17, 2010

Welcome Important Dates Committees Invited Speakers Call for Papers Call for Informal Presentations Participants
Registration Travel Venue Accommodation Climate Accepted papers Program

Measuring Communication in Cellular Automata

Martin Kutrib and Andreas Malcher
Institut für Informatik
Universität Gießen, Germany

Abstract. Parallel computational models are appealing and widely used in order to describe, understand, and manage parallel processes occurring in real life. One principal task in order to employ a parallel computational model in an optimal way is to understand how cooperation of several processors is organized optimally. To this end, it is essential to know which communication and which amount of communication must or should take place between several processors. From the viewpoint of energy and the costs of communication links, it would be desirable to communicate a minimal number of times with a minimum amount of information transmitted. On the other hand, it would be interesting to know how much communication is necessary in a certain parallel model to accomplish a certain task.

Considering the model of cellular automata, the state of each cell is communicated to its neighbors in every time step. That is, on the one hand the state is sent regardless of whether it is really required, and on the other hand, the number of bits sent is determined by the number of states.

For cellular automata where the bandwidth of the communication links between two cells is bounded by some fixed constant, the most restricted setting is one bit bandwidth. However, these cellular automata are still powerful enough to accept unary as well as non-unary non-context-free (even non-semilinear) languages in real time. For some classes it is additionally known that almost all of the commonly investigated decidability problems are undecidable. For real-time one-way cellular automata where the communication is quantitatively measured by counting the number of uses of the communication links between cells, the total sum of all communications or the maximal number of communications that may appear between each two cells can be considered. Reducing the number of communications in such a way that each two neighboring cells may communicate constantly often only, leads to devices which still can accept non-context-free (even non-semilinear) languages. Again, almost all of their decidability questions can be shown to be undecidable.

We will present the main aspects and results regarding computational capacity and decidability issues of cellular automata obeying strict qualitative and quantitative limits on the amount of communication.

Winter picture