Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-15T21:16:07.524Z Has data issue: false hasContentIssue false

Abductive logic programs with penalization: semantics, complexity and implementation

Published online by Cambridge University Press:  10 January 2005

SIMONA PERRI
Affiliation:
Department of Mathematics, University of Calabria, 87030 Rende (CS), Italy (e-mail: [email protected], [email protected])
FRANCESCO SCARCELLO
Affiliation:
DEIS, University of Calabria, 87030 Rende (CS), Italy (e-mail: [email protected])
NICOLA LEONE
Affiliation:
Department of Mathematics, University of Calabria, 87030 Rende (CS), Italy (e-mail: [email protected], [email protected])

Abstract

Abduction, first proposed in the setting of classical logics, has been studied with growing interest in the logic programming area during the last years. In this paper we study abduction with penalization in the logic programming framework. This form of abductive reasoning, which has not been previously analyzed in logic programming, turns out to represent several relevant problems, including optimization problems, very naturally. We define a formal model for abduction with penalization over logic programs, which extends the abductive framework proposed by Kakas and Mancarella. We address knowledge representation issues, encoding a number of problems in our abductive framework. In particular, we consider some relevant problems, taken from different domains, ranging from optimization theory to diagnosis and planning; their encodings turn out to be simple and elegant in our formalism. We thoroughly analyze the computational complexity of the main problems arising in the context of abduction with penalization from logic programs. Finally, we implement a system supporting the proposed abductive framework on top of the DLV engine. To this end, we design a translation from abduction problems with penalties into logic programs with weak constraints. We prove that this approach is sound and complete.

Type
Regular Papers
Copyright
© 2005 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)