人机界面中知识库维护的高效算法

• 作 者: 栾尚敏 戴国忠 程成 陈由迪
• 机 构: 中国科学院软件研究所智能工程实验室
• 出 处: 第十届全国图像图形会议,第一届全国虚拟现实技术研讨会
• 发表日期: 2001年期
• 关键词: 人机界面 知识库维护 多项式时间 子句集 时间复杂性 子集 语法 协调 线性时间 文字 维护算法 基于模型 命题 方法 可求解 证明

本文首先给出了命题Horn型和二文字子句型知识库时的维护算法.对于只存在唯一极小不协调的子集的情况,命题horn子句集和二文字子句集上的基于语法的维护是多项式时间的.若原知识库有唯一模型,基于模型的方法是线性时间可求解的;基于语法的方法,可以在多项式时间内求得部分极大协调的子集.本文还证明了算法的正确性,分析了时间复杂性.