Accession Number : ADA325942

Title :   Computing the Well-Founded Semantics Faster,

Corporate Author : CINCINNATI UNIV OH

Personal Author(s) : Berman, Kenneth A. ; Schlipf, John S. ; Franco, John V.

PDF Url : ADA325942

Report Date : 1991

Pagination or Media Count : 15

Abstract : We address methods of speeding up the calculation of the well-founded semantics for normal propositional logic programs. We first consider two algorithms already reported in the literature and show that these, plus a variation upon them, have much improved worst-case behavior for special cases of input. Then we propose a general algorithm to speed up the calculation for logic programs with at most two positive subgoals per clause, intended to improve the worst case performance of the computation. For a logic program P in atoms A, the speed up over the straight Van Gelder alternating fixed point algorithm (assuming worst-case behavior for both algorithms) is approximately ((absolute value of P)/(absolute value of A)) to the 1/3 power. For absolute value of P greater than or equal to absolute value of A to the 4th power, the algorithm runs in time linear in absolute value of P.

Descriptors :   *ALGORITHMS, DATA BASES, OPTIMIZATION, COMPUTATIONS, COMPUTER LOGIC, SEMANTICS, MATHEMATICAL LOGIC, STRUCTURED PROGRAMMING.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE