A recognition algorithm for deterministic CFLs optimal in time and space
Braunmuhl von Braunmuhl, Rutger Verbeek · 1980
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).