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