1. Inicio
  2. Atrás
Título: An analysis of the computational complexity of DeLP through game semantics
Autores: Cecchi, Laura
Fillottrani, Pablo Rubén
Simari, Guillermo Ricardo
Fecha: 2012-10-26
2005-10
2005-10
Publicador: Unversidad Nacional de La Plata
Fuente:

Tipo: Objeto de conferencia
Objeto de conferencia
Tema: argumentative systems
defeasible reasoning
Logic Programming
Semantics
Games
Ciencias Informáticas
Descripción: 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.
VI Workshop de Agentes y Sistemas Inteligentes (WASI)
Idioma: Inglés