Recognition of Deterministic ET0L Languages in Polynomial Time
DOI:
https://doi.org/10.7146/dpb.v5i63.6482Abstract
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.Downloads
Published
1976-10-01
How to Cite
Jones, N. D., & Skyum, S. (1976). Recognition of Deterministic ET0L Languages in Polynomial Time. DAIMI Report Series, 5(63). https://doi.org/10.7146/dpb.v5i63.6482
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.