Informatik, TU Wien

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 [10].

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

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