Languages not recognizable in real time by one-dimensional cellular automata

摘要

This paper discusses real-time language recognition by one-dimensional cellular automata (CA), focusing on limitations of the parallel recognition power. We investigate language recognition of strings containing binary representations B(|w|) of their own lengths. It is shown that:(1)The language LX={w∈{0,1}+:w contains the binary number(s) B(|w|)} is recognizable by CA in linear time, but is not recognizable in real time; and(2)The class of languages that are recognizable by CA in real time is not closed under concatenation and not closed under reversal. These results are solutions to the problems posed by Smith III in [A.R. Smith III, Real-time language recognition by one-dimensional cellular automata, J. Comput. System Sci. 6 (1972) 233–253].