On the Complexity of Model Checking for Propositional Default Logics: New Results and Tractable Cases

Baumgartner, Robert; Gottlob, Georg

On the Complexity of Model Checking for Propositional Default Logics: New Results and Tractable Cases

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 64-68.

Abstract

We analyse the complexity of standard and weak model checking for propositional default logic; in particular, we solve the open problem of complexity in case of normal default theories and introduce a new ample class of default theories with a tractable model checking problem.

Robert Baumgartner, and Georg Gottlob. 1999. On the Complexity of Model Checking for Propositional Default Logics: New Results and Tractable Cases. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99. IJCAI, 64–68. https://ijcai.org/proceedings/1999/10

@inproceedings{ijcai1999p10,
  title     = {On the Complexity of Model Checking for Propositional Default Logics: New Results and Tractable Cases},
  author    = {Baumgartner, Robert and Gottlob, Georg},
  booktitle = {Proceedings of the Sixteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-99}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Thomas Dean},
  pages     = {64--68},
  year      = {1999},
  note      = {Automated Reasoning},
  url       = {https://ijcai.org/proceedings/1999/10},
}

TY  - CPAPER
TI  - On the Complexity of Model Checking for Propositional Default Logics: New Results and Tractable Cases
AU  - Baumgartner, Robert
AU  - Gottlob, Georg
T2  - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1999
SP  - 64
EP  - 68
UR  - https://ijcai.org/proceedings/1999/10
ER  -