An analysis of the computational complexity of DeLP through game semantics

Abstract

Defeasible Logic Programming (DeLP) is a suitable tool for knowledge representation and reasoning. Its operational semantics is based on a dialectical analysis where arguments for and against a literal interact in order to determine whether this literal is believed by a reasoning agent. The semantics GS is a declarative trivalued game-based semantics for DeLP that is sound and complete for DeLP operational semantics. Complexity theory has become an important tool for comparing different formalism and for helping to improve implementations whenever is possible. For these reasons, it is important to investigate the computational complexity and expressive power of DeLP. In this paper we present a complexity analysis of DeLP through game-semantics GS. In particular, we have determined that computing rigorous consequences is P-complete and that the decision problem “a set of defeasible rules is an argument for a literal under a de.l.p.” is in P.