Computer Science – Logic in Computer Science
Scientific paper
2005-01-25
Theory and Practice of Logic Programming, 5(6):669-711, 2005
Computer Science
Logic in Computer Science
To appear in Theory and Practice of Logic Programming (TPLP). 44 pages
Scientific paper
We advocate a declarative approach to proving properties of logic programs. Total correctness can be separated into correctness, completeness and clean termination; the latter includes non-floundering. Only clean termination depends on the operational semantics, in particular on the selection rule. We show how to deal with correctness and completeness in a declarative way, treating programs only from the logical point of view. Specifications used in this approach are interpretations (or theories). We point out that specifications for correctness may differ from those for completeness, as usually there are answers which are neither considered erroneous nor required to be computed. We present proof methods for correctness and completeness for definite programs and generalize them to normal programs. For normal programs we use the 3-valued completion semantics; this is a standard semantics corresponding to negation as finite failure. The proof methods employ solely the classical 2-valued logic. We use a 2-valued characterization of the 3-valued completion semantics which may be of separate interest. The presented methods are compared with an approach based on operational semantics. We also employ the ideas of this work to generalize a known method of proving termination of normal programs.
Drabent Wlodzimierz
Milkowska M.
No associations
LandOfFree
Proving Correctness and Completeness of Normal Programs - a Declarative Approach does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Proving Correctness and Completeness of Normal Programs - a Declarative Approach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Proving Correctness and Completeness of Normal Programs - a Declarative Approach will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-513143