hide
Free keywords:
-
Abstract:
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 + ).