Cellular automata and formal languages
- 1 October 1970
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 216-224
- https://doi.org/10.1109/swat.1970.4
Abstract
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.Keywords
This publication has 8 references indexed in Scilit:
- Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State MachinesIEEE Transactions on Computers, 1969
- Tessellation AutomataInformation and Control, 1969
- A note on computing time for recognition of languages generated by linear grammarsInformation and Control, 1967
- Recognition and parsing of context-free languages in time n3Information and Control, 1967
- An optimum solution to the firing squad synchronization problemInformation and Control, 1966
- Generation of Primes by a One-Dimensional Real-Time Iterative ArrayJournal of the ACM, 1965
- On the Computational Complexity of AlgorithmsTransactions of the American Mathematical Society, 1965
- Classes of languages and linear-bounded automataInformation and Control, 1964