Universality of reversible hexagonal cellular automata
Morita, Kenichi ; Margenstern, Maurice ; Imai, Katsunobu
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999), p. 535-550 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1999-01-01
@article{ITA_1999__33_6_535_0,
     author = {Morita, Kenichi and Margenstern, Maurice and Imai, Katsunobu},
     title = {Universality of reversible hexagonal cellular automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {33},
     year = {1999},
     pages = {535-550},
     mrnumber = {1747515},
     zbl = {0953.68099},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1999__33_6_535_0}
}

Morita, Kenichi; Margenstern, Maurice; Imai, Katsunobu. Universality of reversible hexagonal cellular automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) pp. 535-550. http://gdmltest.u-ga.fr/item/ITA_1999__33_6_535_0/

[1] C. H. Bennett, Logical reversibility of computation. IBM J. Res. Develop. 17 (1973) 525-532. | MR 449020 | Zbl 0267.68024

[2] C. H. Bennett, Notes on the history of reversible computation. IBM J. Res. Develop. 32 (1988) 16-23. | MR 949739

[3] E. Fredkin and T. Toffoli, Conservative logic, Internat J. Theoret. Phys. 21 (1982) 219-253. | MR 657156 | Zbl 0496.94015

[4] K. Imai and K. Morita, A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theoret. Comput. Sci., to appear. | MR 1739889 | Zbl 0951.68086

[5] N. Margolus, Physics-like model of computation. Physica D 10 (1984) 81-95. | MR 762656 | Zbl 0563.68051

[6] K. Morita and M. Harao, Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE Japan E-72 (1989) 758-762.

[7] K. Morita, A simple construction method of a reversible finite automaton out of Fredkin gates, and its related problem. Trans. IEICE Japan E-73 (1990) 978-984.

[8] K. Morita and S. Ueno, Computation-universal models of two-dimensional 16-state reversible cellular automata. IEICE Trans. Inf. Syst. E75-D (1992) 141-147.

[9] T. Toffoli, Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci. 15 (1 1977) 213-231. | MR 462816 | Zbl 0364.94085

[10] T. Toffoli and N. Margolus, Invertible cellular automata: A Review. Physica D 45 (1990) 229-253. | MR 1094877 | Zbl 0729.68066