
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