ComputingComputer ScienceMathematicsAlgorithmsFormal MethodsAutomata TheoryCellular AutomataComputational ModelsContext-free LanguagesFinite AutomataFormal LanguagesAutomata EquivalenceFinite Automata TheoryLinear Bounded Automata
A set of equivalences is established among cellular automata, iterative acceptors, and linear-bounded automata. However, cellular automata are shown to be inherently faster than iterative acceptors. Many positive results are presented to indicate that the context-free languages can, perhaps, be accepted in time n and space n by cellular automata.
11
Classes of languages and linear-bounded automata
S.-Y. Kuroda · Information and Control · 1964 · 271 citations