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 + ).

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).