Complex Systems

The Enumeration of Preimages and Gardens-of-Eden in Sequential Cellular Automata Download PDF

Yan Deqin
Hou Qinghu
Electronic mail address: hqh@public1.tpt.tj.cn
Research Center for Combinatorics,
Nankai University,
Tianjin 300071, China

Abstract

The enumeration of preimages in sequential cellular automata is approached. Two methods are given to enumerate the preimages of a rule. Preimage enumeration is simplified by using transform matrix expressions. The concept of factor graphs is presented in the study of De Bruijn graphs. A criterion for a rule having gardens-of-Eden is given.