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 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].