Learning Generalized Horn Sentences

本研究探讨了概念课在精确学习模式下的学习问题。这一概念类，即k-拟Horn语句的集合，在这两个模型中都具有至关重要的意义：我们知道，如果k-拟Horn语句被证明在精确学习模型中是可学习的，那么(在一些一般密码假设下)大类合取范式语句在PAC模型中是可预测的。部分研究表明，当确切的学习模型增加一些更大的能力时，k-准喇叭句子确实是可学习的。这一研究将继续下去，以求在确切的学习模型中得到关于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.