Report Number: CS-TR-69-125
Institution: Stanford University, Department of Computer Science
Title: Grammatical complexity and inference
Author: Feldman, Jerome A.
Author: Gips, James
Author: Horning, James J.
Author: Reder, Stephen
Date: June 1969
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. Appendices A and B and
Section 2a.0 are primarily the work of Reder, Sections 2b and
3d of Horning, Section 4 and Appendix C of Gips, and the
remainder the responsibility of Feldman.