Key points are not available for this paper at this time.
There is a context-free language L₀ such that every context-free language is an inverse homomorphic image of L₀ or L₀ - \ e\. Hence the time complexity of recognition of L₀ is the least upper bound for time complexity of recognition of context-free languages. A similar result holds for quasirealtime Turing machine languages. Several languages are given such that deterministic and nondeterministic polynomial time acceptance are equivalent if and only if any one of them is deterministic polynomial time acceptable.
Sheila A. Greibach (Sat,) studied this question.