Towards a Basis for Parallel Language Recognition by Cellular Automata
Katsuhiko Nakamura
This paper investigates several models of the parallel language recognition power, especially limitations of the real-time recognition power, of one-dimensional one-way and two-way cellular automata (CA). The paper focuses on prefix recognition and real-time recognition with the center mark to clarify the relation between recognition power and available positional information. In prefix recognition, each prefix of the input string is accepted if the prefix is a member of the language. In recognition with the center mark, the initial configuration contains not only an input string but also the position of the center of the string.
Keywords: Real-time recognition, linear-time recognition, OCA,prefix recognition.