Normal Form Nested Programs

  • 2009-04-07
  • Research

The extended language of DLP has been introduced by Lifschitz, Tang, and Turner in 1999 and ist called Nested Logic Programming (NLP).

Der Arbeitsbereich Wissensbasierte Systeme des Instituts für Informationssysteme lädt ein.


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 [10]. 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 talk, 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, which is not guaranteed for NFN programs. We identify the class of NFN programs, for which domain independence is guaranteed. Finally, we present an algorithm which transforms NFN programs into DLP programs in a correct and efficient way which allows for using existing DLP systems as computational back-ends.


Note: This is one of the thousands of items we imported from the old website. We’re in the process of reviewing each and every one, but if you notice something strange about this particular one, please let us know. — Thanks!