Recognition of deterministic ETOL languages in logarithmic space
- Jones, Neil D.
- Skyum, Sven
Publication date
November 1977
DOI Publisher
Published by Elsevier Inc. ISSN
0019-9958Abstract
It is shown that if G is a deterministic ETOL system, there is a nondeterministic log space algorithm to determine membership in L(G). Consequently, every deterministic ETOL language is recognizable in polynomial time. As a corollary, all context-free languages of finite index, and all Indian parallel languages are recognizable within the same bounds
Add to ORKG