Universality of reversible hexagonal cellular automata

Kenichi Morita; Maurice Margenstern; Katsunobu Imai

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1999)

  • Volume: 33, Issue: 6, page 535-550
  • ISSN: 0988-3754

How to cite

top

Morita, Kenichi, Margenstern, Maurice, and Imai, Katsunobu. "Universality of reversible hexagonal cellular automata." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 33.6 (1999): 535-550. <http://eudml.org/doc/92619>.

@article{Morita1999,
author = {Morita, Kenichi, Margenstern, Maurice, Imai, Katsunobu},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {hexagonal partitioned cellular automaton; cellular automaton},
language = {eng},
number = {6},
pages = {535-550},
publisher = {EDP-Sciences},
title = {Universality of reversible hexagonal cellular automata},
url = {http://eudml.org/doc/92619},
volume = {33},
year = {1999},
}

TY - JOUR
AU - Morita, Kenichi
AU - Margenstern, Maurice
AU - Imai, Katsunobu
TI - Universality of reversible hexagonal cellular automata
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1999
PB - EDP-Sciences
VL - 33
IS - 6
SP - 535
EP - 550
LA - eng
KW - hexagonal partitioned cellular automaton; cellular automaton
UR - http://eudml.org/doc/92619
ER -

References

top
  1. [1] C. H. Bennett, Logical reversibility of computation. IBM J. Res. Develop. 17 (1973) 525-532. Zbl0267.68024MR449020
  2. [2] C. H. Bennett, Notes on the history of reversible computation. IBM J. Res. Develop. 32 (1988) 16-23. MR949739
  3. [3] E. Fredkin and T. Toffoli, Conservative logic, Internat J. Theoret. Phys. 21 (1982) 219-253. Zbl0496.94015MR657156
  4. [4] K. Imai and K. Morita, A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theoret. Comput. Sci., to appear. Zbl0951.68086MR1739889
  5. [5] N. Margolus, Physics-like model of computation. Physica D 10 (1984) 81-95. Zbl0563.68051MR762656
  6. [6] K. Morita and M. Harao, Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE Japan E-72 (1989) 758-762. 
  7. [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. [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. [9] T. Toffoli, Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci. 15 (1 1977) 213-231. Zbl0364.94085MR462816
  10. [10] T. Toffoli and N. Margolus, Invertible cellular automata: A Review. Physica D 45 (1990) 229-253. Zbl0729.68066MR1094877

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.