An analysis of the computational complexity of DeLP through game semantics

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 semantic...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Cecchi, Laura, Fillottrani, Pablo Rubén, Simari, Guillermo Ricardo
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2005
Materias:
Ciencias Informáticas
Logic Programming
Semantics
Games
argumentative systems
defeasible reasoning
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/23000
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-23000
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Logic Programming
Semantics
Games
argumentative systems
defeasible reasoning
spellingShingle Ciencias Informáticas
Logic Programming
Semantics
Games
argumentative systems
defeasible reasoning
Cecchi, Laura
Fillottrani, Pablo Rubén
Simari, Guillermo Ricardo
An analysis of the computational complexity of DeLP through game semantics
topic_facet Ciencias Informáticas
Logic Programming
Semantics
Games
argumentative systems
defeasible reasoning
description 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.
format Objeto de conferencia
Objeto de conferencia
author Cecchi, Laura
Fillottrani, Pablo Rubén
Simari, Guillermo Ricardo
author_facet Cecchi, Laura
Fillottrani, Pablo Rubén
Simari, Guillermo Ricardo
author_sort Cecchi, Laura
title An analysis of the computational complexity of DeLP through game semantics
title_short An analysis of the computational complexity of DeLP through game semantics
title_full An analysis of the computational complexity of DeLP through game semantics
title_fullStr An analysis of the computational complexity of DeLP through game semantics
title_full_unstemmed An analysis of the computational complexity of DeLP through game semantics
title_sort analysis of the computational complexity of delp through game semantics
publishDate 2005
url http://sedici.unlp.edu.ar/handle/10915/23000
work_keys_str_mv AT cecchilaura ananalysisofthecomputationalcomplexityofdelpthroughgamesemantics
AT fillottranipabloruben ananalysisofthecomputationalcomplexityofdelpthroughgamesemantics
AT simariguillermoricardo ananalysisofthecomputationalcomplexityofdelpthroughgamesemantics
AT cecchilaura analysisofthecomputationalcomplexityofdelpthroughgamesemantics
AT fillottranipabloruben analysisofthecomputationalcomplexityofdelpthroughgamesemantics
AT simariguillermoricardo analysisofthecomputationalcomplexityofdelpthroughgamesemantics
bdutipo_str Repositorios
_version_ 1764820467975192579

Ejemplares similares