Let S(n) be a nice space bound such that log2 n S(n) n. Then every DCFL is recognized by a multitape Turing machine simultaneously in time O(n2/S(n)) and space O(S(n)), and this time bound is optimal. If the machine is allowed a random access input, then the time bound can be improved so that the time-space product is O(n1 + ).

A lower bound for the time-space trade-off of pebble games on PD-Graphs (which represent computations of push-down automata or recursion schemes) is proved, that is only a bit lower than the best known upper bound (the lower and upper time bound is about n · 2 logn/log(s/log n)). The best lower bound known up to now is the bound for linear recursion (about n · log n/log(s/log n) for s ≫ log n.

An algorithm is presented which recognizes arbitrary deterministic CFLs in space O(log2n) and time O(n2/log2n) simultaneously on a deterministic multitape Turing machine. Furthermore, the algorithm provides a general space-time trade-off for deterministic CFLs: the lower bound of the space time product is n2 and our algorithm uses time O(n2/s(n)) for any "acceptable" space functions s(n) between log2n and n. The same methods also give very small upper bounds for DCFL recognition using a fast read-only memory for the input (e.g. space (log n)2 and time n1+ε simultaneously for any ε ≫ o).