Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > A Tight Linear Bound on the Ne...

A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata

Eugen Czeizler, Jarkko Kari, A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata. In: G. F. Italiano L. Monteiro C. Palamidessi M. Yung L. Caires (Ed.), Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), LNCS 3580, 410-420, Springer, 2005.

Abstract:

Reversible cellular automata (RCA) are models of massively parallel computation that preserve information. They consist of an array of identical finite state machines that change their states synchronously according to a local update rule. By selecting the update rule properly the system has been made information preserving, which means that any computation process can be traced back step-by-step using an inverse automaton. We investigate the maximum range in the array that a cell may need to see in order to determine its previous state. We provide a tight upper bound on this inverse neighborhood size in the one-dimensional case: we prove that in a RCA with n states the inverse neighborhood is not wider than n-1, when the neighborhood in the forward direction consists of two consecutive cells. Examples are known where range n-1 is needed, so the bound is tight. If the forward neighborhood consists of m consecutive cells then the same technique provides the upper bound $n^{m-1}-1$ for the inverse direction.

BibTeX entry:

@INPROCEEDINGS{inpCzKa05a,
  title = {A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata},
  booktitle = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005)},
  author = {Czeizler, Eugen and Kari, Jarkko},
  volume = {3580},
  series = {LNCS},
  editor = {L. Caires, G. F. Italiano L. Monteiro C. Palamidessi M. Yung},
  publisher = {Springer},
  pages = {410-420},
  year = {2005},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication