Accession Number : ADA114923

Title :   O (log N) Time Recognition of Deterministic CLFs.

Descriptive Note : Technical rept.,

Corporate Author : HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB

Personal Author(s) : Reif,John H

PDF Url : ADA114923

Report Date : Apr 1982

Pagination or Media Count : 26

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)

Descriptors :   *Computational linguistics, *Context free grammars, *Random access computer storage, Parallel processors, Polynomials, Time, Recognition, Determinants(Mathematics), Algorithms, Acceptability

Subject Categories : Linguistics
      Theoretical Mathematics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE