The completion of a program introduced by Clark is important for giving a declarative semantics to the negation as failure rule and to SLDNF resolution. Essential for having a completeness result is the consistency of the completion. The aim of this work is to give a unifying presentation of several known classes of programs that have consistent completion. The consistency of the completion of a program P is guaranteed by some properties of the graph which represents the dependency relation between the predicate symbols of P (global dependencies), or the ground atoms of the Herbrand basis of P (local dependencies). A taxonomy of program classes which are discriminated by these properties is presented, together with a uniform presentation of the (mostly well-known) techniques of model construction for the programs of each class. In this perspective it is also easier to understand the concept of perfect model and the relation between models of the completion and circumscription. © 1993.

Graph properties for normal logic programs

CORTESI, Agostino;
1993

Abstract

The completion of a program introduced by Clark is important for giving a declarative semantics to the negation as failure rule and to SLDNF resolution. Essential for having a completeness result is the consistency of the completion. The aim of this work is to give a unifying presentation of several known classes of programs that have consistent completion. The consistency of the completion of a program P is guaranteed by some properties of the graph which represents the dependency relation between the predicate symbols of P (global dependencies), or the ground atoms of the Herbrand basis of P (local dependencies). A taxonomy of program classes which are discriminated by these properties is presented, together with a uniform presentation of the (mostly well-known) techniques of model construction for the programs of each class. In this perspective it is also easier to understand the concept of perfect model and the relation between models of the completion and circumscription. © 1993.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10278/26402
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 1
social impact