A real‐time recognition of languages for bounded cellular automata
Hiromi Miyajima · Systems and Computers in Japan · 1989
Abstract With the progress of VLSI technology, researchers are more interested in parallel computation. For example, discussions are made on the parallel processings such as the recognition of language, sorting, matrix computation and graph processing, using the systolic array, the iterative array, and the bounded cellular automaton. It was shown in a previous paper that the bounded cellular automaton is properly faster in the recognition of language than the systolic array, i.e., one‐way cellular automaton. This paper is a continuation of that previous paper, and shows that the bounded cellular automaton can recognize in nearly half the time the class of languages which can be recognized in real time.