暨南大学融媒体中心讯 近日，信息科学技术学院计算机科学系、广东省智慧教育研究院官全龙与方良达课题组所撰写的论文“On the role of logical separability in knowledge compilation”被AIJ期刊所接收，以及“A Multi-Valued Decision Diagram-Based Approach to Constrained Optimal Path Problems over Directed Acyclic Graphs”和“On the Logic of Theory Change lteration of KM-Update, Revised”被IJCAI会议接收。

论文“A Multi-Valued Decision Diagram-Based Approach to Constrained Optimal Path Problems over Directed Acyclic Graphs”，2022级计算机科学系研究生张洺玮为第一作者；方良达副教授及官全龙教授为共同通讯作者；2022级计算机科学系研究生古镇豪及吉林大学赖永副教授为合作作者。许多组合优化问题可以约简为有向无环图上的最优路径问题。最优路径问题的约束版本要求解满足给定的逻辑约束。Nishino等学者提出了一种基于二元决策图的约束搜索算法（BDD-constrained search，BCS），用于求解有向无环图约束最优路径问题。该算法将边看作变量，将约束看作布尔函数，并通过一种布尔函数的紧凑表示——二元决策图来维护约束。但是，BCS算法在搜索过程中存在冗余操作。为了减少这些冗余操作，本研究使用顶点代替边作为变量，并因此使用多值函数表示约束。基于约束的多值函数表示，本研究提出了一种新颖算法：基于多值决策图的约束搜索算法（MDD-constrained search，MCS）。该算法使用一种多值函数的紧凑表示——多值决策图代替了二元决策图。此外，本研究提出多值函数的域约简技术，提高MCS算法的性能。实验结果表明，本研究提出的MCS算法优于BCS算法。

论文“On the role of logical separability in knowledge compilation”，2020级计算机科学系研究生邱俊铭为第一作者，李雯晴为第二作者；方良达副教授及官全龙教授为共同通讯作者；数学系赖兆荣副教授等为合作作者。高效命题逻辑范式是提升高计算复杂性推理问题求解效率的关键，因此如何设计具有强推理以及高简洁性的命题逻辑范式一直是知识表示与推理领域中的重要研究课题。逻辑分离的概念最初由多伦多大学教授Levesque提出，表示一个公式的推理任务可以分解为其子公式的推理任务进行求解。本研究将逻辑分离概念应用于命题逻辑系统中可满足性查询、子句蕴含查询、模型计数查询、模型枚举查询以及变元遗忘转换等多种重要推理操作上，提出相应的逻辑分离性质，并剖析了其在提升推理效率方面的作用机理。基于逻辑分离性质，本研究设计出了可满足性逻辑分离范式、子句蕴含逻辑分离范式和模型计数逻辑分离范式等多种高效命题逻辑范式，并对这些新型逻辑范式的知识编译性质进行了系统的分析，拓展了现有的知识编译图谱。理论分析表明，子句蕴含逻辑分离范式支持高效的变元遗忘操作，并且比大部分现有的同等推理能力的命题逻辑范式更简洁；而模型计数逻辑分离范式在高效求解模型计数问题方面是一种更具通用性的候选目标编译范式。

论文“On the Logic of Theory Change lteration of KM-Update, Revised”方良达副教授为第一作者；2020级计算机科学系研究生朱同为第二作者；官全龙教授及2020级计算机科学系研究生邱俊铭为共同通讯作者；罗伟其教授、数学系赖兆荣副教授、中山大学万海教授为合作作者。信念修正和更新是信念改变的两个重要分支，均旨在研究智能体如何根据新信息修改其信念。它们之间最显著的区别在于前者研究的是静态世界中的信念改变，而后者主要关注动态世界的信念改变。著名的AGM和KM公设被分别提出用于刻画理性的信念修正和更新。然而，它们的约束过于宽松，不足以排除迭代过程中一些不可理的信念改变。为此，DP公设及其扩展被相继提出以描述合理的迭代信念修正行为。进一步地，Ferme和Goncalves将这些公设融合进信念更新中。但是他们提出的关于信念状态和用于语义描述的可信赋值存在一些冗余的组件。更重要的是，他们的方法并没有满足迭代信念更新所要求的理想性质，并且缺乏关于DP公设在信念更新中合理性的讨论。本文旨在弥补他们方法的上述不足。首先，本研究基于信念状态，对原始KM公设作出了修改，并提出了可信集合赋值用于将每个信念状态映射到偏序上。然后，本研究将迭代信念修正中的几个著名的公设迁移到信念更新中。针对每个提出的公设，本研究基于偏序提供了对应的精确语义刻画。最后，本研究分析了这些迭代更新公设和信念更新中KM公设之间的兼容性。

IJCAI（全称 International Joint Conference on Artificial Intelligence）是人工智能领域的国际顶级会议，AIJ（全称 Artificial Intelligence）是人工智能领域的国际顶级期刊，二者被中国计算机学会推荐为A类期刊。近两年AIJ期刊全年接收均不超过150篇论文。

责编：陈国琼