Bin Wang ; Jun Shen ; Shutao Zhang ; Zhizheng Zhang - On the Strong Equivalences for LPMLN Programs

lmcs:5752 - Logical Methods in Computer Science, January 22, 2021, Volume 17, Issue 1 - https://doi.org/10.23638/LMCS-17(1:4)2021
On the Strong Equivalences for LPMLN ProgramsArticle

Authors: Bin Wang ; Jun Shen ; Shutao Zhang ; Zhizheng Zhang

    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 ...


    Volume: Volume 17, Issue 1
    Published on: January 22, 2021
    Accepted on: November 9, 2020
    Submitted on: September 10, 2019
    Keywords: Computer Science - Logic in Computer Science,D.1.6

    Consultation statistics

    This page has been seen 980 times.
    This article's PDF has been downloaded 182 times.