Normal Form Nested Programs

Disjunctive logic programming under the answer set semantics (DLP, ASP) has been acknowledged as a versatile formalism for knowledge representation and reasoning during the last decades. Lifschitz, Tang, and Turner have introduced an extended language of DLP, called Nested Logic Programming (NLP), in 1999 [12]. It often allows for more concise representations by permitting a richer syntax in rule heads and bodies. However, that language is propositional and thus does not allow for variables, one of the strengths of DLP.

In this paper, we introduce a language similar to NLP, called Normal Form Nested (NFN) programs, which does allow for variables, and present the syntax and semantics. However, with the introduction of variables an important issue arises: domain independence, the question of whether the semantics of a program is independent of the considered domain (given that it is sufficiently rich). Domain independence, originally studied for logic-based database query languages, is desirable because it guarantees that the semantics remains equal if unrelated information is added and also ensures finiteness of intended models even if infinite domains are considered. With the presence of variables, NFN programs in general are not domain independent. We study this issue in depth and define the class of safe NFN programs, which are guaranteed to be domain independent.

Moreover, we show that for those NFN programs, which are also NLPs, our semantics coincides with the one of [12], while keeping the standard meaning of answer sets on DLP programs with variables. We also show that our semantics coincides with Herbrand stable models as defined in [6] of formulas corresponding to NFN programs. Finally, we provide an algorithm which transforms NFN programs into DLP programs in a correct and efficient way. We have implemented this algorithm, which provides an effective implementation of the NFN language, using existing DLP systems as a back-end.