Parallel Language Recognition in Constant Time by Cellular Automata

摘要

It is proved that the set of all languages accepted within a fixed, language dependent number of steps by deterministic one dimensional cellular acceptors is a proper subset of the set of all regular languages. A combinatorial condition is stated which is necessary and sufficient for a language to be recognizable in constant time by a deterministic one dimensional cellular automaton. It is shown that the question whether or not the language generated by a given context sensitive grammar is recognizable in constant time is algorithmically unsolvable. The question becomes solvable if a regular grammar is given. Finally it is proved that the set of all languages that can be accepted by non-deterministic one dimensional cellular acceptors is equal to the set of all regular languages. In conclusion some generalizations to n-dimensional languages and array languages are mentioned.