Research activity in 1994
The group began its research activity in the area of Logic Programming by
studying variants of unification algorithms and extensions of logic programming
languages with structuring constructs such as blocks and modules. Later on the
group became interested also in nonmonotonic reasoning, in particular in the
connections between Truth Maintenance Systems and negation by failure in logic
programming.
The most recent research activities are focused on the problem of defining
extensions of logic programming and on non-monotonic reasoning. The two areas
are somewhat connected through the common issue of negation as failure. The
main topics are the following
Modal extensions. The modal extension of logic programming we have
defined provides some reasoning capabilities in a multiagent situation. The
language contains different modalities of the form [ai] to represent agents
beliefs together with a "common knowledge" operator. The language supports
implication embedded in goals, so that some form of hypothetical reasoning can
be performed. This language is well suited for structuring programs with
modules, which can be composed in several ways.
Hypothetical reasoning. We have addressed the problems raised by the
introduction of negation as failure in N-Prolog, a language which allows
hypothetical goals. Moreover, we have defined a logic programming language with
belief revision capabilities, which supports hypothetical updates in presence
of constraints. When facts are added to the program, they are incorporated in
it with the highest priority. If an update violates some integrity constraints
the atoms responsible for the inconsistency and having the least priority are
overruled. This language can be used to define several forms of defeasible
reasoning and it enjoys a logic characterization in a modal logic. It supports
reasoning with multiple sources of information, ordered according to their
reliability.
Classical negation. Usually, the semantics of classical negation in
logic programming resort to syntactic manipulations of programs (negative
literals are translated into new atoms). We have proposed a semantic account of
classical negation based on the idea that different semantics can be obtained
through the standard interpretations of implication in 3-valued logic. As a
result, we obtain a unifying framework and some interesting new semantics, that
enhance the inferential power of extended logic programs without increasing
their computational complexity.
Negation as failure. In addition to the researches already mentioned
above (in relation with hypothetical reasoning and classical negation), another
topic we have focused on concernes the strong relationship between negation as
failure and abduction (first recognized in Eshghi and Kowalski's seminal
work). We have developed three-valued stable model semantics, which is an
extension of the Stable Models semantics, and captures exactly the results of
Eshghi and Kowalski's proof procedure.
Autoepistemic Logic. Autoepistemic logic suffers from well-known
technical problems. When a theory has no stable expansion, no information can
be drawn from the theory, even if its monotonic part is consistent. Secondly,
some beliefs can support themselves, without any further justification.
Finally, it is impossible to have a goal directed proof-procedure. These
problems have been tackled by introducing a three-valued autoepistemic logic,
which has been applied to derive a general unifying framework for many
semantics of logic programs. The same framework allows to link program modules
interpreted through different semantics.
Default logic. We have introduced a uniform syntactic characterization
for some different variants of Reiter's default logics (DL), by making use of a
modal language. We have also defined some new cumulative variants of DL, in the
style of Brewka's Cumulative DL, but with different properties concerning
semimonotonicity and committment to assumptions.
Expressive power of nonmonotonic logics. The problem of encoding
incomplete information into databases is of great interest in the areas of
databases, logic programming and AI. The study of Query Languages (QL's) for
extracting such information is far from complete. We have contributed to this
area by proving some negative results on expressiveness of a large class of
QL's which cover first and second order logic, datalog and extensions thereof
(eg. negation, disjunction) as well as preference based logics, default logic
and autoepistemic logic. Our results show that quering incomplete information
involves novel problems which cannot be tackled with standard techniques.
Another topic of research concerns the definition of goal directed proof
procedures for implicational fragments of modal logics and substructural
logics (relevance logics, linear logic).
The work in nonmonotonic reasoning is strongly related to the area of
Artificial Intelligence, especially to the research activities in the Knowledge
representation and reasoning subarea.
Most of our work has been carried out within the Progetto Finalizzato CNR
"Sistemi Informatici e Calcolo Parallelo" (subprojects "Logic languages" and
"Causal"), the ESPRIT BRA Projects Medlar I and Medlar II "Mechanising
Deduction in the Logics of Practical Reasoning", and the working group LAC
"Logic and Change". In particular, the work on hypothertical updates is carried
out in cooperation with Prof. Gabbay of Imperial College (London).
