
Accession Number : ADA325942
Title : Computing the WellFounded 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 wellfounded 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 worstcase 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 worstcase 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