一句话：研究一元析取 Datalog、MMSNP 与 ALC 本体查询到 FO、MDLog、Datalog 的可重写性，给出可判定性与复杂度。
本文研究一元析取 Datalog 程序、MMSNP 语句的补以及基于 ALC 族表达性描述逻辑和合取查询的本体中介查询（OMQ）的可重写性，即这些查询能否等价转换为 FO、一元 Datalog（MDLog）或 Datalog。作者证明到 FO 和 MDLog 的可重写性可判定，并在原查询满足与相等性有关的条件时证明到 Datalog 的可重写性也可判定。除 MDLog 情形仍介于 2NExpTime 与 3ExpTime 之间外，所研究问题均为 2NExpTime 完全。文章还分析重写形状（MMSNP 情形对应 obstruction），并给出一种比已有构造更初等、且适用于含自由变量公式的规范 Datalog 程序构造。
We study rewritability of monadic disjunctive Datalog programs, (the complements of) MMSNP sentences, and ontology-mediated queries (OMQs) based on expressive description logics of the ALC family and on conjunctive queries. We show that rewritability into FO and into monadic Datalog (MDLog) are decidable, and that rewritability into Datalog is decidable when the original query satisfies a certain condition related to equality. We establish 2NExpTime-completeness for all studied problems except rewritability into MDLog for which there remains a gap between 2NExpTime and 3ExpTime. We also analyze the shape of rewritings, which in the MMSNP case correspond to obstructions, and give a new construction of canonical Datalog programs that is more elementary than existing ones and also applies to formulas with free variables.
@article{paperbot791,
title = {Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics},
author = {Cristina Feier and Antti Kuusisto and Carsten Lutz},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 2},
year = {2019},
doi = {10.23638/lmcs-15(2:15)2019}
}