DocumentCode
2201239
Title
Cellular automata and formal languages
Author
Smith, Alvy Ray, III
fYear
1970
fDate
28-30 Oct. 1970
Firstpage
216
Lastpage
224
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
Automata; Formal languages; Nearest neighbor searches; Pattern recognition; Strips; Turing machines;
fLanguage
English
Publisher
ieee
Conference_Titel
Switching and Automata Theory, 1970., IEEE Conference Record of 11th Annual Symposium on
Conference_Location
USA
ISSN
0272-4847
Type
conf
DOI
10.1109/SWAT.1970.4
Filename
4569650
Link To Document