Accession Number : AD0707755

Title :   BOUNDS ON THE COMPLEXITY OF GRAMMARS.

Descriptive Note : Technical rept.,

Corporate Author : MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER

Personal Author(s) : Snively,James W. , Jr

Report Date : MAY 1970

Pagination or Media Count : 76

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.

Descriptors :   (*PATTERN RECOGNITION, PROGRAMMING LANGUAGES), (*PROGRAMMING LANGUAGES, *PHRASE STRUCTURE GRAMMARS), VOCABULARY, SYNTAX, COMPUTATIONAL LINGUISTICS, CONTEXT FREE GRAMMARS, CONTEXT SENSITIVE GRAMMARS

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE