---
title: "On the Complexity of Model Checking for Propositional Default Logics: New Results and Tractable Cases"
authors:
  - "Robert Baumgartner"
  - "Georg Gottlob"
doi: ""
url: "https://ijcai.org/proceedings/1999/10"
pdf: "https://ijcai.org/proceedings/1999/0010.pdf"
venue: "Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence"
year: 1999
pages: "64-68"
track: "Automated Reasoning"
keywords:
---

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

Robert Baumgartner, Georg Gottlob

*Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence*, 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.