O (log N) Time Recognition of Deterministic CLFs.
John H. Reif · 1982
Abstract : We prove that the languages accepted by auxiliary deterministic pushdown machines with space s(n) greater than or equal to log n and time 2O(s(n)) are accepted in time O(s(n)) by parallel RAMs. Thus deterministic context free languages are accepted in time O (log n) and a polynomial number of processors by parallel RAMs. Also, we show that the languages accepted in time T(n) by parallel RAMs are accepted with simultaneous space T(n) and time 2O(T(n)2) by auxiliary deterministic pushdown machines. (Author)