|
Published Articles >> Table of Contents >> Abstract
19th Annual IEEE Symposium on Logic in Computer Science (LICS'04)
pp. 367-376
An Algebraic Approach to the Complexity of Propositional Circumscription
Gustav Nordh, Linköpings Universitet, Sweden
Peter Jonsson, Linköpings Universitet, Sweden
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2004.1319631
Send link to a friend
| Abstract |
|
Every logical formalism gives rise to two fundamental problems: model checking and inference. Circumscription is one of the most important and well studied formalisms in the realm of nonmonotonic reasoning. The model checking and inference problem for propositional circumscription has been extensively studied from the viewpoint of computational complexity. We use a new approach based on algebraic techniques to study the complexity of the model checking and inference problems for propositional variable circumscription in a unified way. We prove that there exists a dichotomy theorem for the complexity of the inference problem in propositional variable circumscription. We also study the model checking and inference problem for propositional variable circumscription in many-valued logics using the same algebraic techniques. In particular we prove dichotomy theorems for the complexity of model checking and inference for propositional variable circumscription in the case of 3-valued logic.
|
 Additional Information
|
Citation:
Gustav Nordh, Peter Jonsson,
"An Algebraic Approach to the Complexity of Propositional Circumscription,"
lics,
pp. 367-376,
19th Annual IEEE Symposium on Logic in Computer Science (LICS'04),
2004
|
|
