Abductive Logic Programs with Penalization: Semantics, Complexity and
  Implementation
  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.
