Cellular automata and formal languages

Name: Cellular automata and formal languages
Creator: Alvy Ray Smith
Keywords: 0202 electrical engineering, electronic engineering, information engineering, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences

descriptionPublicationkeyboard_double_arrow_right Article 01 Oct 1970Publisher:IEEEJournal:11th Annual Symposium on Switching and Automata Theory (swat 1970)

Authors: Alvy Ray Smith;

doi: 10.1109/swat.1970.4

Cellular automata and formal languages

- Summary
- Metrics

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.

Related Organizations

New York University
United States

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	48
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average