One-way nondeterministic real-time list-storage languages
Seymour Ginsburg, Michael A. Harrison · Journal of the ACM · 1968
A device is presented which has its memory organized as a linear list, a type of storage equivalent to having two pushdown stores. Attention is then focused on the nondeterministic automaton (called an lsa ) which results when the input is read one-way and the device operates in real-time. The set of words (called a language ) accepted by an lsa is extensively studied. In particular, several characterizations and closure properties of languages are given.