一句话：提出 LPMLN 程序的 p-强等价并给出模型论刻画、复杂性及化简条件，系统研究其强等价性质。
LPMLN 将答案集编程（ASP）的非单调推理与 Markov 逻辑网络（MLN）的概率推理相结合。本文研究 LPMLN 程序的强等价，提出 p-强等价概念并给出模型论刻画，考察其与已有 LPMLN 强等价定义的关系。随后从四方面展开：针对程序重写提出两种松弛等价及刻画；分析判定强等价的计算复杂性；建立 LPMLN 强等价与带弱约束和有序析取的 ASP 扩展之间的联系；利用 p-强等价进行程序化简，并给出判定单条 LPMLN 规则与空程序 p-强等价的语法条件。结果有助于理解 LPMLN 程序、通过翻译研究其他逻辑形式体系的强等价，并改进 LPMLN 求解器实现。
LPMLN is a powerful knowledge representation and reasoning tool that combines the non-monotonic reasoning ability of Answer Set Programming (ASP) and the probabilistic reasoning ability of Markov Logic Networks (MLN). In this paper, we study the strong equivalence for LPMLN programs, which is an important tool for program rewriting and theoretical investigations in the field of logic programming. First of all, we present the notion of p-strong equivalence for LPMLN and present a model-theoretical characterization for the notion. And we investigate the relationships among the p-strong equivalence and other existing notions of strong equivalences for LPMLN. Then, we investigate several properties of the p-strong equivalence from the following four aspects. Firstly, we investigate two relaxed notions of the p-strong equivalence according to practical scenarios of program rewriting, and present corresponding characterizations for the notions. Secondly, we analyze the computational complexities of deciding strong equivalences for LPMLN programs. Thirdly, we investigate the relationships among the strong equivalences of LPMLN and two extensions of ASP: ASP with weak constraints and ordered disjunctions. Finally, we investigate LPMLN program simplification via the p-strong equivalence and present some syntactic conditions that decide the p-strong equivalence between a single LPMLN rule and the empty program. The contributions of the paper are as follows. Firstly, all of the results presented in this paper provide a better understanding of LPMLN programming, which helps us further explore the properties of LPMLN. Secondly, the relationships among the strong equivalences open a way to study the strong equivalences for some logic formalisms by translating into LPMLN. Thirdly, the program simplification can be used to enhance the implementations of the LPMLN solvers ...
@article{paperbot1349,
title = {On the Strong Equivalences for LPMLN Programs},
author = {Bin Wang and Jun Shen and Shutao Zhang and Zhizheng Zhang},
journal = {Logical Methods in Computer Science},
volume = {Volume 17, Issue 1},
year = {2021},
doi = {10.23638/lmcs-17(1:4)2021}
}