## 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 AutomataMartin Kutrib and Andreas MalcherInstitut für Informatik Universität Gießen, Germany
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. |

jac2010@lists.utu.fi |