Accession Number:

AD0692390

Title:

GRAMMATICAL COMPLEXITY AND INFERENCE

Descriptive Note:

Technical rept.

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Report Date:

1969-06-01

Pagination or Media Count:

107.0

Abstract:

The problem of inferring a grammar for a set of symbol strings is considered and a number of new decidability results obtained. Several notions of grammatical complexity and their properties are studied. The question of learning the least complex grammar for a set of strings is investigated leading to a variety of positive and negative results. This work is part of a continuing effort to study the problems of representation and generalization through the grammatical inference question.

Subject Categories:

  • Linguistics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE