One-way nondeterministic real-time list-storage languages
- 1 July 1968
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 15 (3), 428-446
- https://doi.org/10.1145/321466.321475
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- Real-Time Definable LanguagesJournal of the ACM, 1967
- One-way stack automataJournal of the ACM, 1967
- Stack automata and compilingJournal of the ACM, 1967
- A formal semantics for computer languages and its application in a compiler-compilerCommunications of the ACM, 1966
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965
- A New Normal-Form Theorem for Context-Free Phrase Structure GrammarsJournal of the ACM, 1965
- Real time computationIsrael Journal of Mathematics, 1963
- Automatic syntactic analysis and the pushdown storeProceedings of Symposia in Applied Mathematics, 1961
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959
- Formal Reductions of the General Combinatorial Decision ProblemAmerican Journal of Mathematics, 1943