Compiling defeasible inheritance networks to general logic programs

AbstractWe present a method of compiling arbitrary defeasible (inheritance) networks to general logic programs. We show a one-to-one correspondence between the credulous extensions of a defeasible network and the stable models of the translated logic program. This result leads to the discovery that an elegant query answering procedure for Horty's credulous extensions had long existed: the abductive proof procedure formulated by Eshghi and Kowalski for general logic programs is sound and complete for acyclic defeasible networks under the proposed translation. Since the translation is faithful to the commonly accepted notion of specificity, it leads to a novel transformational approach: any semantics defined for general logic programs yields an extension semantics for networks, and any query answering procedure developed for general logic programs can be used to answer queries for networks under the same semantics. This approach also yields new insights into the difficulties confronting path-based formalisms. Essentially, reasoning with logic programs overcomes the difficulty with path-based formalisms in dealing with the interactions of cascaded effects of link sequences, possibly compounded by preemption of paths. This difficulty has been particularly evident in the past in trying to understand the meaning of the networks that involve cycles, both semantically and proof-theoretically, and in the “directly skeptical” approach to defeasible inheritance