Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata
verfasst von : Eugen Czeizler, Jarkko Kari
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.