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):

Report Date:

1982-04-01

Pagination or Media Count:

26.0

Abstract:

We prove that the languages accepted by auxiliary deterministic pushdown machines with space sn greater than or equal to log n and time 2Osn are accepted in time Osn 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 Tn by parallel RAMs are accepted with simultaneous space Tn and time 2OTn2 by auxiliary deterministic pushdown machines. Author

Subject Categories:

  • Linguistics
  • Theoretical Mathematics
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE