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

DOI:
https://doi.org/10.1090/S0002-9939-1976-0444346-6

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.

**[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)**

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

Retrieve articles in all journals with MSC: 94A30

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1976-0444346-6

Keywords:
Cellular automata,
tessellation structures,
parallel maps,
parallel relations,
self-reproducing,
Garden-of-Eden

Article copyright:
© Copyright 1976
American Mathematical Society