On the Complexity of ID/LP Parsing,

Abstract

Recent linguistic theories cast surface complexity as the result of interacting subsystems of constraints. For instance, the ID/LP grammar formalism separates constraints on immediate dominance from those on linear order, Shieber (1983) has shown how to carry our direct parsing of ID/LP grammars. His algorithm uses ID and LP constraints directly in language processing, without expanding them into a context-free 'object grammar'. This report examines the computational difficulty of ID/LP parsing; the worst-case runtime of his algorithm is exponential in grammar size. A reduction of the vortex-cover problem proves that ID/LP parsing is NP-complete. The growth of internal data structures is the source of difficulty in Shieber's algorithm. The computational and linguistic implications of these results are discussed. Despite the potential for combinatorial explosion, Shieber's algorithm remains better than the alternative of parsing an expanded object grammar.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1984
Accession Number
ADA158211

Entities

People

  • G. E. Barton Jr

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Acquisition
  • Algorithms
  • Artificial Intelligence
  • Buildings And Structures
  • Computational Complexity
  • Construction
  • Context Free Grammars
  • Contracts
  • Explosions
  • Grammars
  • Language
  • Linguistics
  • Military Research
  • Natural Languages
  • Notation
  • Standards
  • Symbols

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Operations Research
  • Theoretical Analysis.