Fast recognition of pushdown automaton and context-free languages

We prove: (1) every language accepted by a two-way nondeterministic pushdown automaton can be recognized on a random access machine in O(n3/log n) time; (2) every language accepted by a loop-free two-way nondeterministic pushdown automaton can be recognized in O(n3/log2 n) time; (3) every context-free language can be recognized on-line in O(n3/log2 n) time. We improve the results of Aho, Hopcroft, and Ullman (Inform. Contr. 13, 1968, 186–206), Rytter (Inform. Process. Lett. 16, 1983, 127–129), and Graham, Harrison, and Ruzzo (ACM Trans. Programm. Lang. Systems 2, No. 3, 1980, 415–462)