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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/69/125/CS-TR-69-125.pdf