Extended Well-Founded Semantics in Bilattices

One of the most used assumptions in logic programming and deductive databases is the so-called Closed World Assumption (CWA), according to which the atoms that cannot be inferred from the programs are considered to be false (i.e. a pessimistic assumption). One of the most successful semantics of conventional logic programs based on the CWA is the well-founded semantics. However, the CWA is not applicable in all circumstances when information is handled. That is, the well-founded semantics, if conventionally defined, would behave inadequately in different cases. The solution we adopt in this paper is to extend the well-founded semantics in order for it to be based also on other assumptions. The basis of (default) negative information in the well-founded semantics is given by the so-called unfounded sets. We extend this concept by considering optimistic, pessimistic, skeptical and paraconsistent assumptions, used to complete missing information from a program. Our semantics, called extended well-founded semantics, expresses also imperfect information considered to be missing/incomplete, uncertain and/or inconsistent, by using bilattices as multivalued logics. We provide a method of computing the extended well-founded semantics and show that Kripke-Kleene semantics is captured by considering a skeptical assumption. We show also that the complexity of the computation of our semantics is polynomial time.

Authors:

• Daniel Stamate

Keywords:

• Logic programs
• imperfect information
• multivalued logics
• bilattices
• assumptions.

References:

[1] ARIELI, O. and AVRON, A. The Logical Role of the Four-Valued
Bilattice, Proc. 13th Annual IEEE Symp. on Logic in Computer Science,
118-126, 1998
[2] BIDOIT N., FROIDEVEAUX C., Negation by default and unstratifiable
logic programs, TCS, 78, 1991
[3] BELNAP, N. D., Jr, A Useful Four-Valued Logic, in: J. M. Dunn and
G. Epstein (eds.), Modern Uses of Multiple-valued Logic, D. Reichel,
Dordrecht, 1977.
[4] DAMASIO, C. and PEREIRA, L., A survey of paraconsistent semantics
for logic programas, in: D. Gabbay and P. Smets (eds.), Handbook of
Defeasible Reasoning and Uncertainty Management Systems, vol. 2,
Kluwer, 1998.
[5] FITTING, M. C., A Kripke/Kleene Semantics for Logic Programs, J.
Logic Programming, 2:295-312, 1985
[6] FITTING, M. C., Bilattices and the Semantics of Logic Programming, J.
Logic Programming, 11:91-116, 1991
[7] FITTING, M. C., The Family of Stable Models, J. Logic Programming,
17:197-225, 1993
[8] FITTING, M. C., Fixpoint semantics for logic programming - a survey,
Theoretical Computer Science, 278:25-51, 2002
[9] GINSBERG,M. L., Multivalued Logics: a Uniform Approach to Reasonning
in Artificial Intelligence, Computationnal Intelligence, 4:265-316,
1988.
[10] GINSBERG, M. L., Bilattices and modal operators, J. of Logic Computation,
1:41-69, 1990.
[11] LOYER, Y., SPYRATOS, N., and STAMATE,D., Computing and Comparing
Semantics of Programs in Four-valued Logics, in: Proceedings of
the 24th Symposium on Mathematical Foundations of Computer Science
(MFCS'99), LNCS 1672, Springer Verlag, 1999
[12] LOYER Y., SPYRATOS N. and STAMATE D. Parameterised Semantics for
Logic Programs - a Unifying Framework, Theoretical Computer Science,
308(1-3), 429-447, 2003
[13] LOYER Y., SPYRATOS N. and STAMATE D. Hypothesis-based semantics
of logic programs in multivalued logics, ACM Transactions on Computational
Logic 15(3), 508-527, 2004
[14] PRZYMUSINSKI, T. C. The well-founded semantics coincides with the
three-valued stable semantics, Fundamenta Informaticae, 13(4):445-464,
1990
[15] VAN GELDER, A., ROSS, K. A., SCHLIPF, J. S., The Well-Founded
Semantics for General Logic Programs, J. ACM, 38:620-650, 1991
[16] SIM K. M. Bilattices and Reasoning in Artificial Intelligence: Concepts
and Foundations Artificial Intelligence Review 15:3, 219-240, 2001