BOUNDS ON THE COMPLEXITY OF GRAMMARS.

Abstract

In the study of the theory of image processing by computer, with emphasis on the theory of 'picture grammars', a problem of particular interest is that of how simple a grammar for a given language can be; a one-dimensional version of the problem is treated in the document. Three implicit measures of the complexity of a phrase structure grammar are: the length of the longest member of a rule of the grammar, the size of the vocabulary of the grammar, and the number of rules of the grammar. Upper and lower bounds on these measures are sought for grammars that generate a given language.

Document Details

Document Type
Technical Report
Publication Date
May 01, 1970
Accession Number
AD0707755

Entities

People

  • James W. Snively Jr

Organizations

  • University of Maryland

Tags

DTIC Thesaurus Topics

  • Computers
  • Cooperation
  • Grammars
  • Image Processing
  • Information Processing
  • Language
  • Linguistics
  • Phrase Structure Grammars
  • Vocabulary

Readers

  • Computational Linguistics
  • Operations Research