Grammatical complexity and inference
Grammatical complexity and inference
复制标题
语法复杂性和推理
DOI：
--
复制
发表时间：
1969
期刊：
影响因子：
--
通讯作者：
S. Reder
中科院分区：
文献类型：
--
作者：
J. Feldman;J. Gips;J. Horning;S. Reder
推断一组符号串的语法的问题被认为是一些新的可判定性的结果。研究了语法复杂性的几个概念及其性质。学习最不复杂的语法为一组字符串的问题进行了调查，导致各种积极和消极的结果。这项工作是一个持续努力的一部分，研究问题的代表性和概括通过语法推理的问题。附录A和B以及第2a.0节主要是Reder的工作，Horning的第2B和3d节，Gips的第4节和附录C，其余部分由Feldman负责。
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.