Affiliations: Department of Mathematics University of Calabria,
Italy. E-mail: {a.bria,faber,leone}@mat.unical.it
Abstract: 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.
