Expressiveness of Logic Programs under General Stable Model Semantics
This work provides foundational insights into the computational limits of answer set programming, which is incremental but clarifies theoretical boundaries for logic programming researchers.
The paper investigates the expressiveness of normal and disjunctive logic programs under general stable model semantics, showing that over finite structures, some disjunctive programs cannot be translated to normal programs under certain arity bounds, and that this expressiveness equivalence coincides with whether NP is closed under complement.
The stable model semantics had been recently generalized to non-Herbrand structures by several works, which provides a unified framework and solid logical foundations for answer set programming. This paper focuses on the expressiveness of normal and disjunctive programs under the general stable model semantics. A translation from disjunctive programs to normal programs is proposed for infinite structures. Over finite structures, some disjunctive programs are proved to be intranslatable to normal programs if the arities of auxiliary predicates and functions are bounded in a certain way. The equivalence of the expressiveness of normal programs and disjunctive programs over arbitrary structures is also shown to coincide with that over finite structures, and coincide with whether NP is closed under complement. Moreover, to capture the exact expressiveness, some intertranslatability results between logic program classes and fragments of second-order logic are obtained.