On the circuit depth of structurally Reversible Cellular Automata

• Autorzy: Kari J.
• Języki publikacji: EN

Abstrakty

EN

We study the family of structurally reversible cellular automata that use the (generalized) Margolus neighborhoods. We show that every reversible cellular automaton (RCA) can be embedded into the standard two layer Margolus neighborhood defined by two overlapping square partitions of the cellular space and two one-to-one local rules. The embedding allows step-by-step simulations. Then we investigate how many layers of one-to-one local rules are required in exact representations of RCA. We show how in the d-dimensional cellular space any consecutive d+2 layers can be combined into d+1 layers. This proves that no more than d+1 layers are necessary. We demonstrate that in the two-dimensional case d=2 the number d+1 is optimal by providing an example of an RCA with three layers of local rules that cannot be expressed in two layers.

Słowa kluczowe

EN

cellular automata; reversible computation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1999
• Tom: Vol. 38, Nr 1,2
• Strony: 93--107
• Opis fizyczny: wykr., bibliogr. 9 poz.

Twórcy

autor

Kari J.

• Department of Computer Science , 14 MacLean Hall, University of Iowa City, IA 52242, USA,