Computing the Well-Founded Semantics Faster,

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1991
Accession Number
ADA325942

Entities

People

  • John S. Schlipf
  • John V. Franco
  • Kenneth A. Berman

Organizations

  • University of Cincinnati

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Construction
  • Databases
  • Language
  • Lists (Data Structures)
  • Military Research
  • Semantics
  • Standards

Readers

  • Analytical Mechanics
  • Artificial Intelligence
  • Graph Algorithms and Convex Optimization.