Complexity of DeLP: Current Status and Moving Forward

PABLO R. FILLOTTRANI; LAURA CECCHI

Argumentation-based Proofs of Endearment

College Publications

Año: 2018; p. 123 - 144

Defeasible Logic Programming (DeLP) is a general argumentation based system for knowledge representation and reasoning. Its proof theory 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 GS semantics is a declarative trivalued game-based semantics for DeLP that is sound and complete for DeLP proof theory. In this paper we review the latest complexity results of some important decision problems of DeLP under GS, and extend some of them. Furthermore, we introduce DeLP as a query language and we study data and combined complexity of query answering in the context of DeLP for some important problems. As far as we know, data and combined complexity have not been introduced in the context of argumentation systems.