English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  DetailsSummary

Released
Conference Paper

The Computational Value of Joint Consistency

MPS-Authors
/persons/resource/persons44325

Dimopoulos,  Yannis
Programming Logics, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Dimopoulos, Y. (1994). The Computational Value of Joint Consistency. In C. MacNish, D. Pearce, & L. M. Pereira (Eds.), Logics in Artificial Intelligence: Proceedings of the JELIA'94 (pp. 50-65). Berlin, Germany: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-ADAE-6
Abstract
In this paper we investigate the complexity of some recent reconstructions of Reiter's Default Logic using graph-theoretical structures. It turns out that requiring joint consistency of the justification of the applied rules has serious effects on the computational features of default reasoning. Namely, many of the intractability problems of Reiter's original approach, in some cases disappear in the new frameworks. However, interesting problems remain intractable. We also present a propositional semantics for those approaches, stemming from the translation of the graph structures into propositional logic. Finally, the constraint stable model semantics is introduced, and proved to be related to the notion of joint consistency.