Faster recognition of languages for bounded cellular automata
Hiromi Miyajima · Systems and Computers in Japan · 1987
Abstract Advancement of VLSI technology accelerates studies in parallel computation. These are studies of such parallel algorithms as recognition of language, sorting, matrix calculations and graph processing, of one‐way cellular automata (systolic arrays), iterative arrays, tree structure cell automata, and bounded cellular automata, etc., the goal of which is to devise simpler and faster networks. So far, systolic arrays have attracted considerable attention from theoretical as well as practical viewpoints. On the other hand, bounded cellular automata seemingly have not stimulated much interest. This paper shows that bounded cellular automata process recognition of languages faster than one‐way automata.