Learning Generalized Horn Sentences

本研究探讨了概念类的学习， 精确学习模型 这个概念类，k-拟 角句，具有至关重要的意义，在这两个模型：它 已知如果k-拟Horn语句被证明是 在精确的学习模型中是可学习的，那么（在一些 一般密码学假设）的大类 连接范式句子在PAC中是可预测的 模型 部分研究表明，k-拟Horn语句 当精确的学习模型是 增加了更多的力量。 这一系列研究 将继续获得关于 精确学习中k-拟Horn语句的可学性 模型

This research addresses the learning of a concept class in the exact learning model. This concept class, the set of k-quasi Horn sentences, has crucial significance in both models: it is known that if k-quasi Horn sentences are shown to be learnable in the exact learning model, then (under some general cryptographic assumptions) the large class of conjunctive normal form sentences are predictable in the PAC model. Partial research has shown that k-quasi Horn sentences are indeed learnable when the exact learning model is augmented with somewhat more power. This line of research will be continued to obtain a definitive answer about the learnability of k-quasi Horn sentences in the exact learning model.