Green, Frederic NP-complete problems in cellular automata. (English) Zbl 0648.68067 Complex Syst. 1, No. 3, 453-474 (1987). An example of a cellular automaton (CA) is given in which the following problems are NP-complete: (i) determining if a given subconfiguration s can be generated after \(| s|\) time steps, (ii) determining if a given subconfiguration s will recur after \(| s|\) time steps, (iii) determining if a given temporal sequence of states s can be generated in \(| s|\) time steps. It is also found that the CA constructed has an NP-hard limit language. Cited in 15 Documents MSC: 68Q80 Cellular automata (computational aspects) 68Q25 Analysis of algorithms and problem complexity Keywords:cellular automaton; NP-complete; NP-hard limit language PDFBibTeX XMLCite \textit{F. Green}, Complex Syst. 1, No. 3, 453--474 (1987; Zbl 0648.68067)