Parallel Time 0(log N) Acceptance of Deterministic CFLs.

Abstract

This document gives a parallel random access memory algorithm for simulating a deterministic pushdown automaton. On an input of length n,a DPDA will use time O(n); this simulation requires time O(log n) and only polynomially many processors. The algorithm can be easily adapted to accept the 1.R(k) languages as well. Additional keywords: configurations; theorems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1984
Accession Number
ADA152255

Entities

People

  • J. H. Reif
  • P. N. Klein

Organizations

  • Harvard University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Automata
  • Classification
  • Computations
  • Computer Science
  • Contracts
  • Language
  • Machines
  • Military Research
  • Notation
  • Parallel Computing
  • Recognition
  • Security
  • Simulations
  • Translations
  • Universities

Readers

  • Computer Science.
  • Graph Algorithms and Convex Optimization.
  • Mathematical Modeling and Probability Theory.