The complexity of propositional closed world reasoning and circumscription

1994/04/01 by Marco Cadoli, Maurizio Lenzerini · 2 citations
Computer Science · #Bayesian Modeling and Causal Inference #Logic, Reasoning, and Knowledge #Semantic Web and Ontologies

paper · doi:10.1016/s0022-0000(05)80004-2

crossref issued 1994/04/01 · crossref published 1994/04/01 · crossref published-print 1994/04/01 · openalex publication_date 1994/04/01 · crossref created 2005/08/20 · crossref deposited 2019/01/22 · openalex created_date 2025/10/10 · crossref indexed 2026/07/14 · openalex updated_date 2026/07/23

Citations

• Closed-world databases and circumscription
• Propositional circumscription and extended closed-world reasoning are ΠP2-complete
• A theory of diagnosis from first principles

Cited by

• A Note on Reasoning on DL-Lite_{\cal R} with Defeasibility
• Closed-world assumption [wikipedia]