Extended Well-Founded Semantics in Bilattices

Authors: Daniel Stamate

Abstract:

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.

Keywords: Logic programs, imperfect information, multivalued logics, bilattices, assumptions.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062140

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