On Some Open Problems in the Theory of Cellular Automata
S. Rao Kosaraju · IEEE Transactions on Computers · 1974
Some open problems in the theory of cellular automata are considered: the tradeoff between machine complexity and interconnection complexity, linear time pattern recognition and transformation problems, and the noncomputability of the constant of linearity of linear time problems.