Geodesic
On the structure of the set of reversible cellular automata
Diskretnaya Matematika, Tome 19 (2007) no. 3, pp. 102-121.

Voir la notice de l'article provenant de la source Math-Net.Ru

We investigate the structure of the set of reversible cellular automata. In the class of two-dimensional binary linear cellular automata with variable structure, the classes with decidable and undecidable reversibility property are separated, which contain almost all such cellular automata. With the use of this result, we prove undecidability of reversibility in the class of cellular automata with $\Gamma$-pattern and sixteen states of a cell and in the class of two-dimensional binary cellular automata with self-dual local transition functions. The complete description is given for the structure of the set of reversible cellular automata of the class of binary cellular automata with local transition functions from the Post classes. 
@article{DM_2007_19_3_a8,
     author = {I. V. Kucherenko},
     title = {On the structure of the set of reversible cellular automata},
     journal = {Diskretnaya Matematika},
     pages = {102--121},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_3_a8/}
}
TY  - JOUR
AU  - I. V. Kucherenko
TI  - On the structure of the set of reversible cellular automata
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 102
EP  - 121
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_3_a8/
LA  - ru
ID  - DM_2007_19_3_a8
ER  - 
%0 Journal Article
%A I. V. Kucherenko
%T On the structure of the set of reversible cellular automata
%J Diskretnaya Matematika
%D 2007
%P 102-121
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2007_19_3_a8/
%G ru
%F DM_2007_19_3_a8
I. V. Kucherenko. On the structure of the set of reversible cellular automata. Diskretnaya Matematika, Tome 19 (2007) no. 3, pp. 102-121. http://geodesic.mathdoc.fr/item/DM_2007_19_3_a8/

[1] Kudryavtsev V. B., Podkolzin A. S., Bolotov A. A., Osnovy teorii odnorodnykh struktur, Nauka, Moskva, 1990 | MR

[2] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, Moskva, 1985 | MR

[3] Yablonskii S. V., Gavrilov G. P., Kudryavtsev V. B., Funktsii algebry logiki i klassy Posta, Nauka, Moskva, 1966 | MR | Zbl

[4] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Vysshaya shkola, Moskva, 2002

[5] Kucherenko I. V., “O chisle obratimykh odnorodnykh struktur”, Diskretnaya matematika, 15:2 (2003), 123–127 | MR | Zbl

[6] Kucherenko I. V., “O svoistve obratimosti binarnykh kletochnykh avtomatov”, Trudy XXVI Konferentsii molodykh uchenykh, Mekhaniko-matem. f-t MGU, Moskva, 2004, 155–158

[7] Kucherenko I. V., “O razreshimosti obratimosti kletochnykh avtomatov”, Intellektualnye sistemy, 8:1–4 (2003), 465–482

[8] Amoroso S., Patt Y. N., “Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures”, J. Computer and System Sci., 6:5 (1972), 448–464 | MR | Zbl

[9] Kari J., “Reversibility of 2D cellular automata is undecidable”, Physica D, 45 (1994), 379–385 | DOI | MR

[10] Toffoli T., “Computation and construction universality of reversible cellular automata”, J. Computer and System Sci., 15:2 (1977), 213–231 | MR | Zbl

[11] Sutner K., “Linear cellular automata and de Bruijn automata”, Cellular automata: a parallel model, eds. Delorme M., Mazoyer J., Kluwer, Dordrecht, 1998, 303–319 | MR

[12] Durand B., “Inversion of 2D cellular automata: some complexity results”, Theoretical Computer Sci., 134:2 (1994), 387–401 | DOI | MR | Zbl