Recognition of Deterministic ET0L Languages in Polynomial Time

Neil D. Jones; Sven Skyum

doi:10.7146/dpb.v5i63.6482

Recognition of Deterministic ET0L Languages in Polynomial Time

Authors

Neil D. Jones
Sven Skyum

DOI:

https://doi.org/10.7146/dpb.v5i63.6482

Abstract

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.

Author Biographies

Neil D. Jones

Sven Skyum

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