Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Inverse and injectivity of parallel relations induced by cellular automata

Author: Takeo Yaku
Journal: Proc. Amer. Math. Soc. 58 (1976), 216-220
MSC: Primary 94A30
MathSciNet review: 0444346
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Moore and Myhill showed that Garden-of-Eden theorem [2], [3]. A binary relation over the configurations is said to be ``parallel'' if it is induced by a cellular (tessellation) automaton. Richardson showed the equivalence between a parallel relation (a nondeterministic parallel map) with the quiescent state to be injective and its inverse to be parallel by the Garden-of-Eden theorem plus compactness of product topology [4]. This paper deals with the inverse and the injectivity when a cellular automaton is given that induces a parallel relation. We give an equivalent condition, concerning only the local map, for the inverse of a parallel relation to be parallel. Furthermore we show an equivalent condition, concerning only the local map, for the injectivity of a parallel map. Consequently, we note that these two conditions are represented by semirecursive predicates.

References [Enhancements On Off] (What's this?)

  • [1] S. Amoroso and G. Cooper, The Garden-of-Eden theorem for finite configurations, Proc. Amer. Math. Soc. 26 (1970), 158-164. MR 43 # 1760. MR 0276007 (43:1760)
  • [2] E. F. Moore, Machine models of self-reproduction, Proc. Sympos. Appl. Math., vol. 14, Amer. Math. Soc., Providence, R. I., 1962, pp. 17-33.
  • [3] J. Myhill, The converse of Moore's Garden-of-Eden theorem, Proc. Amer. Math. Soc. 14 (1963), 685-686. MR 27 #5698. MR 0155764 (27:5698)
  • [4] D. Richardson, Tessellations with local transformations, J. Comput. System Sci. 6 (1972) 373-388. MR 47 #8220. MR 0319678 (47:8220)
  • [5] T. Yaku, The constructibility of a configuration in a cellular automaton, J. Comput. System Sci. 7 (1973), 481-496. MR 48 #10724. MR 0332397 (48:10724)
  • [6] -, Surjectivity of nondeterministic parallel maps induced by nondeterministic cellular automata, J. Comput. System Sci. 12 (1976), 1-5. MR 0416802 (54:4871)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 94A30

Retrieve articles in all journals with MSC: 94A30

Additional Information

Keywords: Cellular automata, tessellation structures, parallel maps, parallel relations, self-reproducing, Garden-of-Eden
Article copyright: © Copyright 1976 American Mathematical Society

American Mathematical Society