REPRESENTATION OF REVERSIBLE CELLULAR-AUTOMATA WITH BLOCK PERMUTATIONS

Authors
KARI J
Citation
J. Kari, REPRESENTATION OF REVERSIBLE CELLULAR-AUTOMATA WITH BLOCK PERMUTATIONS, Mathematical systems theory, 29(1), 1996, pp. 47-61
Citations number
12
Categorie Soggetti
System Science","Mathematics, Pure","Computer Science Theory & Methods",Mathematics
Journal title
Mathematical systems theory → ACNP
ISSN journal
00255661
Volume
29
Issue
1
Year of publication
1996
Pages
47 - 61
Database
ISI
SICI code
0025-5661(1996)29:1<47:RORCWB>2.0.ZU;2-U
Abstract
We demonstrate the structural invertibility of all reversible one- and two-dimensional cellular automata. More precisely, we prove that ever y reversible two-dimensional cellular automaton can be expressed as a combination of four block permutations, and some shift-like mappings. Block permutations are very simple functions that uniformly divide con figurations into rectangular regions of equal size and apply a fixed p ermutation on all regions.