Parallel String Parsing Using Lattice Graphs.

Abstract

Given a grammar G and a string sigma, all possible parses of sigma can be constructed by repeatedly applying the rules of G in parallel. This process creates a 'lattice graph' in which any directed path from the least element to the greatest element is a sentential form that occurs in a (partial) parse of sigma. Examples are given illustrating how, at least for some grammars, this process does not lead to a combinatorial explosion, and could thus be used to parse strings very rapidly if suitable parallel hardware were available. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1981
Accession Number
ADA105028

Entities

People

  • Azriel Rosenfeld

Organizations

  • University of Maryland

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Air Force
  • Computer Science
  • Computer Vision
  • Computers
  • Context Free Grammars
  • Explosions
  • Formal Languages
  • Grammars
  • Language
  • Maryland
  • Parallel Computing
  • Parallel Processing
  • Scientific Research
  • Sequences
  • Universities

Fields of Study

  • Mathematics

Readers

  • Computational Linguistics
  • Parallel and Distributed Computing.