O (log N) Time Recognition of Deterministic CLFs.

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1982
Accession Number
ADA114923

Entities

People

  • John Reif

Organizations

  • Harvard University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Grammars
  • Language
  • Linguistics
  • Machines
  • Military Research
  • New York
  • Parallel Computing
  • Programming Languages
  • Recognition
  • Simulations
  • Theory Of Computation

Readers

  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Materials Science.
  • Theoretical Analysis.

Technology Areas

  • Space
  • Space - Orbital Debris