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