paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Model Comparison Games for Horn Description Logics

Horn 描述逻辑的模型比较博弈
LICS 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2019匹配度 1/10 · 该论文是纯描述逻辑/模态逻辑理论工作,研究 Horn 描述逻辑的模型比较博弈、可定义性与表达完全性,与用户关注的 LLM/Agent、机器学习系统静态分析、浮点程序分析、贝叶斯程序分析均无直接关联;仅与形式化验证的逻辑基础有非常间接的联系。引用 2 inbox
Jean Christoph Jung, Fabio Papacchini, Frank Wolter, Michael Zakharyaschev
crossref: 2026-09-12

AI 速览

一句话:为 Horn 描述逻辑 hornALC 引入模型比较博弈,给出可定义性与表达完全性结果,并证明其不可区分性检查为 ExpTime 完全。

Horn 描述逻辑是标准描述逻辑中对应一阶 Horn 片段的句法片段,其本体中介查询回答在数据复杂度下为 PTime。本文为基本 Horn 描述逻辑 hornALC(对应基本 Horn 模态逻辑)引入模型比较博弈,并据此建立 Ehrenfeucht–Fraïssé 型可定义性结果和 van Benthem 型表达完全性结果,同时给出后者的有限模型论版本。作者进一步利用该可定义性结果证明 hornALC 模型不可区分性检查是 ExpTime 完全的,这与 ALC 的不可区分性(即互模拟等价)可在 PTime 检查形成鲜明对比。最后,文章定义一阶 Horn 守卫片段并引入相应模型比较博弈,以探索更强描述逻辑与模态逻辑的 Horn 片段。

问题
Horn 描述逻辑与模态逻辑缺少刻画其表达力和模型不可区分性的模型比较博弈;本文研究 hornALC 及更强 Horn 片段的语义刻画与复杂度。
方法
为 hornALC 引入模型比较博弈,建立 Ehrenfeucht–Fraïssé 型可定义性与 van Benthem 型表达完全性,并扩展到一阶 Horn 守卫片段。
评估
通过博弈证明 hornALC 不可区分性检查为 ExpTime 完全,并与 ALC 的 PTime 互模拟等价形成对比;同时给出表达完全性的有限模型论版本。
原文摘要(Abstract)

Horn description logics are syntactically defined fragments of standard description logics that fall within the Horn fragment of first-order logic and for which ontology-mediated query answering is in PTime for data complexity. They were independently introduced in modal logic to capture the intersection of Horn first-order logic with modal logic. In this paper, we introduce model comparison games for the basic Horn description logic hornALC (corresponding to the basic Horn modal logic) and use them to obtain an Ehrenfeucht-Fraïssé type definability result and a van Benthem style expressive completeness result for hornALC. We also establish a finite model theory version of the latter. The Ehrenfeucht-Fraïssé type definability result is used to show that checking hornALC indistinguishability of models is ExpTime-complete, which is in sharp contrast to ALC indistinguishability (i.e., bisimulation equivalence) checkable in PTime. In addition, we explore the behavior of Horn fragments of more expressive description and modal logics by defining a Horn guarded fragment of first-order logic and introducing model comparison games for it.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot5004,
  title = {Model Comparison Games for Horn Description Logics},
  author = {Jean Christoph Jung and Fabio Papacchini and Frank Wolter and Michael Zakharyaschev},
  booktitle = {LICS},
  year = {2019},
  doi = {10.1109/lics.2019.8785658}
}