Real-time recognition of cyclic strings by one-way and two-way cellular automata
This paper discusses real-time language recognition by 1-dimensional one-way cellular automata (OCAs) and two-way cellular automata (CAs), focusing on limitations of the parallel computation power. To clarify the limitations, we investigate real-time recognition of cyclic strings of the form u(k) with u is an element of {0, 1}(+) and k greater than or equal to 2. We show a version of pumping lemma for recognizing cyclic strings by OCAs, which can be used for proving that several languages are not recognizable by OCAs in real time. The paper also discusses the real-time language recognition of CAs by prefix and postfix computation, in which every prefix or postfix of an input string is also accepted, if the prefix or postfix is in the language. It is shown that there are languages L subset of or equal to Sigma(+) such that L is not recognizable by OCA in real-time and the reversal of L and the concatenation LSigma* are recognizable by CA in real-time.
cellular automata oca pumping lemma parallel language recognition prefix recognition