Computing the Well-Founded Semantics: A Summary

Title: Computing the Well-Founded Semantics: A Summary

Research Question: How can the well-founded semantics of logic programs with negation be computed efficiently?

Methodology: The researchers studied extensions and modifications of the alternating-fixpoint approach, a method used to compute the well-founded semantics. They focused on programs with rules that have no more than one positive occurrence of an atom in their bodies. They proposed a new implementation of the alternating-fixpoint method, where false atoms are computed in a top-down fashion.

Results: They showed that their algorithm is faster than other known algorithms and that for a wide class of programs, it is linear and thus, asymptotically optimal.

Implications: This research has implications for the field of logic programming and automated reasoning. The proposed algorithm is faster and more efficient than previous methods, making it a valuable tool for computing the well-founded semantics of logic programs with negation. Additionally, the algorithm can be used as a powerful lookahead mechanism in systems that compute stable models of DATALOG¬programs.

Link to Article: https://arxiv.org/abs/0101014v1 Authors: arXiv ID: 0101014v1