In this paper we have dened a language for hypothetical and counterfactual reasoning. The language is based on a conditional logic and it supports hypothetical insertions in a knowledge base that may contain integrity constraints. The language relies on a revision mechanism which, on the basis of priority information, restores the knowledge base consistency when a violation occurs. We have provided a logical characterization of the language based on abduction, and an abductive proof procedure. Moreover we have shown how this language is related to belief revision theory, by comparing it with Nebel's prioritized base revision.
This paper extends the work in 22] where a more restricted language was studied, in which only hypo-thetical insertions of single atomic formulas were allowed, and whose semantics was based on a completion construction. Here we have considered more complex updates by sets of hypotheses. We had therefore to cope with the possibility of having alternative (equally plausible) revisions of the knowledge base. These alternative revisions can be captured by an abductive approach. The abductive approach we have pre-sented is modular with respect to the adopted monotonic logic. A similar approach has been followed in
2] to dene a language based on a modal logic for reasoning about actions.
In 33] it is shown that prioritized base revision is expressively equivalent to skeptical provability in Brewka's LDT's(level default theories)8], which provide a generalization of Poole's system with priorities.
Therefore, when programs do not contain conditional formulas, we can establish a correspondence between our language and Brewka's LDT.
On the other hand, a similar correspondence does not hold with the prioritized extensions of default logic introduced by Brewka in 9, 10]. In such default logics a partial ordering between default rules is allowed. Moreover, in 10], reasoning about priorities can be modelled, since priority information can be explicitly represented in the logical language by naming default rules.
In this paper we have used a conditional logic as the logical basis of our language. There are other approaches which instead rely on the use of modal logics. For instance, the language presented in 18], contains a modal operator assumeL] (where L is a literal) to represent addition and deletion of atomic formulas. Our proposal is also related to 12], where the problem of reasoning with multiple sources of information is studied for the case when the knowledge sources are (consistent) sets of positive and negative literals, and there is no underlying (protected) theory. Also in 12] a modal language is adopted.
The problem of combining theories and resolving inconsistencies among them has also been studied in 3]. In particular, 3] analyzes the problem of combining prioritized (rst order) theories, T1 T2 :::Tk IC where the priority relation is a total order, and a set of integrity constraints IC has the highest priority. Two approaches are devised: bottom-upand top-down. With the bottom-up approach T1 is combined with T2, with preference to T25 the result is combined with T3, and so on, until the result is combined with Tk, and, nally, with IC. Referring to the example 1.1 in the introduction, let us consider the eect of adopting a bottom up approach in our language6. With a bottom-up approach the query
forange coat, no hat, pink mercedesg>(fblack coat, no hatg>(light coat>suspect Je))
4In the language studied in 26] programs and goals can be mutually nested this is not permitted in this language.
53] discusses several functions to combine theories, based on the computationof maximalconsistent subsets. In particular,
T
1 is combined withT2, with preference toT2 by taking all the theories obtained by adding toT2 a maximal subset ofT1 consistent withT2.
6Remember that, while in 3] the ordered theories contain general formulas (and, in particular, rules), in our language ordered theories contain only sets of atoms, while there is a common protected theory .
fails from the program. In fact,orange coatis overridden by the more reliable informationblack coat, which, in turn, is overridden by the more reliable informationlight coat. Sinceorange coatis deleted,suspect Je
cannot be concluded. The operational semantics of the language presented in 20] is essentially based on this bottom-up approach. However, the case addressed in 20] is much simpler then the one in 3], since each theory contains a single formula.
The top-down approach amounts to start combining Tkwith IC (with preference to IC), then combining Tk;1 with the result (with preference for the last one), and so on, up to T1. The top-down approach is the one we have adopted in this paper. Coming back to the example above, since the most preferred fact light coatoverridesblack coat, the factorange coatis not deleted and, hence,suspect Jecan be concluded.
As observed in 3], top-down combining is more informative then bottom-up combining (in the example, orange coatis deleted in the bottom-up approach but not in the top-down one).
In our language the nonmonotonicbehaviour is achieved through the dierent priorities of sets of updates.
A somewhat similar approach is followed in the languageOrdered Logic (O L) 31, 32]. A program in this language is a monotonic extended logic program, where negated literals can occur also in the head of rules. The nonmonotonic behaviour is obtained by partitioning the program into a set ofcomponents, each consisting of a set of rules, organized into an inheritance hierarchy. If two rules in two dierent components have contradictory conclusions A and:A, then the rule which is more specic in the hierarchy overrules the other one.
Of course, since the hierarchy of components is a partial ordering, it may happen that two conicting rules belong to two components which are not related in the hierarchy. In this case there will be two equally acceptable solutions. In 11] a stable model semantics is dened forO L, and an eective method, using backtracking and nondeterminism, is proposed for computingO Lstable models.
The problem of composing logical theories is also addressed in 1], which deals with updates of knowledge bases represented as sequences of logic programs. Programs may contain default negation not only in the body of clauses but also in their heads. The paper presents a program transformation which takes a sequence of programs and produces a unique program with new propositional variables, which allow the priority of rules to be explicitly represented. The resulting program does no longer contain default negation in the head of clauses. Moreover, default negation is contained only in the body of special \persistency"
rules, which model persistency of atoms through the priority levels.
Both languages use a \top-down" approaches, similar to the one we adopt in this paper. The main dierence between our language and the previous ones is that they do not allow hypothetical reasoning, and thus dependencies among components are determined statically. On the other hand, our language does not allow to specify a partial ordering among sets of updates, but only a total ordering dynamically built.
Another dierence is that in our language we can update programs only by adding atoms and not clauses. However we have shown that this is not a signicant dierence, since we can achieve the same eect by giving names to the rules. Furthermore, in our language we have integrity constraints, and thus an atom can be assumed to persist if ?is not derived. On the other hand, in the other approaches, an atom can be assumed only if its negation does not hold.
The language we have dened is also related to other logic programming languages dealing with explicit negation and constraints, and faced with the problem of removing contradictions when they occur. In particular, Pereira et al. in 36] present a contradiction removal semantics and, in 37], a proof-procedure (similar to an abductive procedure) for extended logic programs with explicit negation and integrity con-straints.
In 14] a capability ofhypothetical query answering against embedded implications with integrity con-straints is introduced into the framework of deductive databases. Embedded implications are transformed into (query equivalent) deductive databases with null values, and a methodology for hypothetical query answering from the resulting databases is described. Integrity constraints are used as a way of eliminat-ing irrelevant hypotheses (only relevant hypotheses which render the situation queried about possible are produced).
Kakas et al. in 29] propose a logic programming language without negation as failure based on the idea of dening a priority relation on the rules of a program, whose semantics is given in terms of the acceptability semantics discussed in Section 4.
In dening our language we have chosen a specic policy to deal with updates. In particular, more recent updates are given a higher priority than the previous ones. In principle, however, other policies might be
used. For instance, updates with the lowest priority could be allowed, and this could be useful to deal with default assumptions which are expected to have a lower priority than other kinds of assumptions in updates. Of course, these extensions of the language would require a modication of the logic on which the language is based, and, in particular, a modication of the conditions (a) and (b) in the denition of the abductive semantics, that are ad hoc for the chosen policy. By contrast, allowing clauses in the revisable part of the program, would only require a minor extension of the language.
ACKNOWLEDGEMENTS
We are grateful to the anonymous referees for their careful reading of the paper, their useful suggestions and constructive criticisms.REFERENCES
1. J.J. Alferes, J.A. Leite, L.M. Pereira, H. Przymusinska, T. C. Przymusinski. Dynamic logic programming.
InProc. of the 6th Int. Conf. on Principles of Knowledge Representation and Reasoning - KR 98, pp.98{109, Trento, Italy, June 1998.
2. M. Baldoni, L. Giordano, A. Martelli, and V. Patti. An Abductive Proof Procedure for Reasoning about Actions in Modal Logic Programming. In J. Dix, L. M. Pereira, and T. C. Przymusinski, editors, Proc. of the 2nd International Workshop on Non-Monotonic Extensions of Logic Programming, NMELP'96, volume 1216 ofLNAI, pages 132{150. Springer-Verlag, 1997.
3. C. Baral, S. Kraus, J. Minker, V. S. Subrahmanian. Combining knowledge bases consisting of rst-order theories. Computational Intelligence, vol.8, n.1, pp. 45{71, 1992.
4. M. Baldoni, L.Giordano, and A.Martelli. A multimodal logic to dene modules in logic programming. In Proc. 1993 International Logic Programming Symposium, pages 473{487, Vancouver, 1993.
5. A. W. Bollen, Relevant Logic Programming. J. Automated Reasoning, 7: 563{585, 1991.
6. A. Bondarenko, F. Toni, R. A. Kowalski. An assumption based framework for non-monotonic reasoning. in Proc. 2nd Int. Workshop on Logic Programming and Non-monotonic Reasoning, 1993.
7. A. J. Bonner. A logical semantics for hypothetical rulebases with deletion. InThe Journal of Logic Pro-gramming, vol.32, no.2, pages 119{170, 1997.
8. G. Brewka. Preferred Subtheories: An Extended Logical Framework for Default Reasoning. InIJCAI-89, pp.1043{1048, 1989, Detroit.
9. G. Brewka. Adding Priorities and Specicity in Default Logic. InJELIA94, Springer LNAI 838, pp.247{260, 1994.
10. G. Brewka. Reasoning about Priorities in Default Logic. InAAAI-94, 1994, pp.940{945.
G. Brewka. Preferred Subtheories: An Extended Logical Framework for Default Reasoning. In IJCAI-89, pp.1043{1048, 1989, Detroit.
11. F. Buccafurri and N. Leone and P. Rullo Stable Models and their Computation for Logic Programming with Inheritance and True Negation. Journal of Logic Programming, vol 27, n. 1, pp.5 - 43, 1996. 1995.
12. L. Cholvy. Proving theorems in a multi-source environment. In Proc. IJCAI-93, pages 66{71, Chambery, 1993.
13. L. Cholvy. A logical approach to multi-sources reasoning. InKnowledge Representation and Reasoning under Uncertainty{LNAI 808, pages 183{196 , 1994.
14. F. Dong, A. Lakshmanan, A Deductive Approach to Hypothetical Query Answering. Proc. of the 1993 International Logic Programming Symposium, 1993, pp. 609-628.
15. P. M. Dung. Negations as hypotheses: an abductive foundation for logic programming. InProc. ICLP-91 Conference, pages 3{17, 1991.
16. P. M. Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning and logic programming. InProc. IJCAI93, pages 852{857, 1993.
17. K. Eshghi and R. Kowalski. Abduction compared with negation by failure. In Proc. 6th ICLP, pages 234{254, Lisbon, 1989.
18. L. Fari~nas del Cerro and A. Herzig. An automated modal logic for elementary changes. In P. Smets et al., editor,Non-standard Logics for Automated Reasoning. Academic Press, 1988.
19. D. M. Gabbay and N. Reyle. NProlog: An extension of Prolog with hypothetical implications.I. Journal of Logic Programming, (4):319{355, 1984.
20. D. Gabbay, L. Giordano, A. Martelli, and N. Olivetti. Conditional logic programming. InProc. 11th ICLP, Santa Margherita Ligure, pages 272{289, 1994.
21. D. Gabbay, L Giordano, A. Martelli, and N. Olivetti. Hypothetical updates, priority and inconsistency in a logic programming language. InProc. LPNMR-95, LNAI 928, pages 203{216, 1995.
22. D. Gabbay, L. Giordano, A. Martelli, and N. Olivetti. A Language for handling Hypothetical Updates and Inconsistency. Journal of the Interest Group in Pure and Applied Logic (IGPL), 4(3):385{416, 1995.
23. P. Gardenfors, Knowledge in ux: modeling the dynamics of epistemic states, MIT Press, Cambridge, Massachussets, 1988.
24. M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In Fifth International Conference and Symposium on Logic Programming, pages 1070{1080, Seattle, 1988.
25. M. Gelfond and V. Lifschitz. Logic programs with classical negation. In Proc. ICLP-90, pages 579{597, Jerusalem, 1990.
26. L. Giordano and N. Olivetti Combining Negation as failure and Embedded Implications in Logic Programs.
Journal of Logic Programming, 36(2): 91{147, 1998.
27. L. Giordano, A. Martelli, M. L. Sapino" An Abductive Proof Procedure for Conditional Logic Programming.
Proc. International Conference on Formal and Applied Practical Reasoning - FAPR96 -LNAI, 1996, Bonn, pp. 231-245.
28. J. Hodas and D. Miller. Logic programming in a fragment of intuitionistic linear logic. J. of Information and Computation, 110(2):327-367, 1994.
29. A.C. Kakas, P. Mancarella, P.M. Dung. The acceptability semantics for logic programs. InProc. 11th ICLP, Santa Margherita Ligure, pages 504{519, 1994.
30. K. Kunen, Signed Data Dependencies in Logic Programs,in J. Logic Programming 7:231-245 (1989).
31. E. Laenens and D. Sacca and D. Vermeir Extending Logic Programming. Proc. of ACM SIGMOD, pp.184{
193, May, 1990. 1993.
32. N. Leone and P. Rullo. Ordered logic programming with sets. J. of Logic and Computation, 3(6):621{642, 1993.
33. B. Nebel. Belief Revision and Default Reasoning: Syntax-Based Approaches. In2nd Int. Conf. on Principles of Knowledge Representation and Reasoning, 1991, pp.417-428.
34. S. Naqvi and F. Rossi. Reasoning in inconsistent databases. InProc. of the 1990 North American Conf. on Logic Programming, pages 255{272, 1990.
35. D. Nute,Topics in Conditional Logic, Reidel, Dordrecht, 1980.
36. L.M. Pereira, J.J. Alferes, J.N. Aparicio Contradiction Removal within the Well Founded Semantics. Proc.
LPNMR-91, (1991) 105{119.
37. L. M. Pereira, J. N. Aparicio, J. J. Alferes, Derivation Procedures for Extended Stable Models. Proc.
IJCAI-91 Conference, 1991, pp. 863-868.
38. L.M. Pereira, C.V. Damasio, J.J. Alferes Diagnosis and Debugging as Contradiction Removal.Proc. LPNMR-93, (1993) 316{330.
39. T. C. Przymusinski. Extended stable semantics for normal and disjunctive programs. in Proc. ICLP90 Conference, pp. 459-477, 1990.
40. G. Sartor Normative conicts in legal reasoning. Articial Intelligence and Law, 1:209{235, 1992.
41. F. Toni and A. Kakas. Computing the acceptability semantics. In Proc. LPNMR-95, pages 401{415, 1995.