Recognition of Deterministic ET0L Languages in Polynomial Time - Jones, Neil D.; Skyum, Sven (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.