Recognition of Deterministic ET0L Languages in Polynomial Time
Neil Deaton Jones, Sven Skyum · DAIMI Report Series · 1976
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.