Minimum and maximum predicates in logic programming
Šumit Ganguly, Sergio Greco, Carlo Zaniolo · 1991
A novel approach is proposed for ezpressing and computing efficiently a large class of problems, including finding the shortest path in a graph, that were previously considered impervious to an efficient treatment in the declarative framework of logic-based languages. Our approach is based on the use of rain and max predicates having a first-order semantics defined using rules with negation in their bodies. We show that when cer- tain monotonictry conditions hold then (1) there ezists a totM well-founded model for these programs contain- ing negation, () this model can be computed efciently using a procedure called greedy flxpoint, and (3) the original program can be rewritten into a more efficient one by pushing rain and max predicates into recursion.