{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T22:31:04Z","timestamp":1784068264126,"version":"3.55.0"},"reference-count":41,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1994,4,1]],"date-time":"1994-04-01T00:00:00Z","timestamp":765158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":7047,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[1994,4]]},"DOI":"10.1016\/s0022-0000(05)80004-2","type":"journal-article","created":{"date-parts":[[2005,8,20]],"date-time":"2005-08-20T07:18:35Z","timestamp":1124522315000},"page":"255-310","source":"Crossref","is-referenced-by-count":43,"title":["The complexity of propositional closed world reasoning and circumscription"],"prefix":"10.1016","volume":"48","author":[{"given":"Marco","family":"Cadoli","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maurizio","family":"Lenzerini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(05)80004-2_bib1","article-title":"Introduction to logic programming","volume":"Vol. B","author":"Apt","year":"1990"},{"key":"10.1016\/S0022-0000(05)80004-2_bib2","series-title":"Readings in Knowledge Representation","first-page":"41","article-title":"A fundamental trade-off in knowledge representation and reasoning","author":"Brachman","year":"1985"},{"key":"10.1016\/S0022-0000(05)80004-2_bib3","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0004-3702(91)90005-5","article-title":"The computational complexity of abduction","volume":"49","author":"Bylander","year":"1991","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib4","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0020-0190(92)90049-2","article-title":"The complexity of model checking for circumscriptive formulae","volume":"44","author":"Cadoli","year":"1992","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0022-0000(05)80004-2_bib5","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/0004-3702(92)90051-X","article-title":"An efficient method for eliminating varying predicates from a circumscription","volume":"54","author":"Cadoli","year":"1992","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib6","series-title":"Proceedings, Pacific Rim International Conference on Artificial Intelligence (PRICAI-90)","first-page":"760","article-title":"Circumscription and nonmonotonic inheritance","author":"Cadoli","year":"1990"},{"key":"10.1016\/S0022-0000(05)80004-2_bib7","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0743-1066(93)90029-G","article-title":"A survey on complexity results for nonmonotonic logics","volume":"17","author":"Cadoli","year":"1993","journal-title":"J. Logic Programming"},{"key":"10.1016\/S0022-0000(05)80004-2_bib8","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/0004-3702(89)90018-0","article-title":"Eliminating the fixed predicates from a circumscription","volume":"39","author":"de Kleer","year":"1989","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib9","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","article-title":"Linear-time algorithms for testing the satisfiability of propositional Horn formulae","volume":"1","author":"Dowling","year":"1984","journal-title":"J. Logic Programming"},{"key":"10.1016\/S0022-0000(05)80004-2_bib10","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0304-3975(93)90073-3","article-title":"Propositional circumscription and extended closed world reasoning are IT2p-complete","volume":"114","author":"Eiter","year":"1993","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(05)80004-2_bib11","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1137\/0205048","article-title":"On the complexity of timetable and multicommodity flow problems","volume":"5","author":"Even","year":"1976","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(05)80004-2_bib12","series-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0022-0000(05)80004-2_bib13","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(86)90001-9","article-title":"Negation as failure: Careful closure procedure","volume":"30","author":"Gelfond","year":"1986","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib14","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0004-3702(89)90068-4","article-title":"On the relationship between circumscription and negation as failure","volume":"38","author":"Gelfond","year":"1989","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib15","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0004-3702(89)90026-X","article-title":"A circumscriptive theorem prover","volume":"39","author":"Ginsberg","year":"1989","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib16","series-title":"Proceedings, Eight Biennal Conference of the Canadian Society for Computational Studies of Intelligence (CSCSI '90)","article-title":"On the theorem provers for circumscription","author":"Inoue","year":"1990"},{"key":"10.1016\/S0022-0000(05)80004-2_bib17","article-title":"A catalog of complexity classes","volume":"Vol. A","author":"Johnson","year":"1990"},{"key":"10.1016\/S0022-0000(05)80004-2_bib18","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0004-3702(91)90011-8","article-title":"Hard problems for simple default logics","volume":"49","author":"Kautz","year":"1991","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/78935.78936","article-title":"Some computational aspects of circumscription","volume":"37","author":"Kolaitis","year":"1990","journal-title":"Assoc. Comput. Mach."},{"key":"10.1016\/S0022-0000(05)80004-2_bib20","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0022-0000(91)90033-2","article-title":"Why not negation by fixpoint?","volume":"43","author":"Kolaitis","year":"1991","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(05)80004-2_bib21","series-title":"Proceedings, 4th International Symposium on Methodologies for Intelligent Systems (ISMIS-89)","first-page":"448","article-title":"On the circumscriptive semantics of inheritance networks","author":"Krishnaprasad","year":"1989"},{"key":"10.1016\/S0022-0000(05)80004-2_bib22","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0004-3702(85)90055-4","article-title":"Closed-world databases and circumscription","volume":"27","author":"Lifschitz","year":"1985","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib23","series-title":"Proceedings, Ninth International Joint Conference on Artificial Intelligence (IJCAI-85)","first-page":"121","article-title":"Computing circumscription","author":"Lifschitz","year":"1985"},{"key":"10.1016\/S0022-0000(05)80004-2_bib24","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0004-3702(80)90011-9","article-title":"Circumscription\u2014A form of non-monotonic reasoning","volume":"13","author":"McCarthy","year":"1980","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib25","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0004-3702(86)90032-9","article-title":"Applications of circumscription to formalizing common-sense knowledge","volume":"28","author":"McCarthy","year":"1986","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib26","series-title":"Proceedings, Sixth Conference on Automated Deduction (CADE-82)","first-page":"292","article-title":"On indefinite databases and the closed world assumption","author":"Minker","year":"1982"},{"key":"10.1016\/S0022-0000(05)80004-2_bib27","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0743-1066(90)90031-Y","article-title":"Minimal consequence in sentential logic","volume":"9","author":"Papalaskari","year":"1990","journal-title":"J. Logic Programming"},{"key":"10.1016\/S0022-0000(05)80004-2_bib28","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0004-3702(89)90067-2","article-title":"An algorithm to compute circumscription","volume":"38","author":"Przymusinski","year":"1989","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib29","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/BF00248321","article-title":"Weak generalized closed world assumption","volume":"5","author":"Rajasekar","year":"1989","journal-title":"J. Automated Reasoning"},{"key":"10.1016\/S0022-0000(05)80004-2_bib30","series-title":"Logic and Data Bases","first-page":"119","article-title":"On closed world data bases","author":"Reiter","year":"1978"},{"key":"10.1016\/S0022-0000(05)80004-2_bib31","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0004-3702(80)90014-4","article-title":"A logic for default reasoning","volume":"13","author":"Reiter","year":"1980","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib32","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(87)90062-2","article-title":"A theory of diagnosis from first principles","volume":"32","author":"Reiter","year":"1987","journal-title":"Artif. Intell. J."},{"key":"10.1016\/S0022-0000(05)80004-2_bib33","series-title":"Proceedings, 10th ACM Symposium on Theory of Computing (STOC-78)","first-page":"216","article-title":"The complexity of satisfiability problems","author":"Schaefer","year":"1978"},{"key":"10.1016\/S0022-0000(05)80004-2_bib34","series-title":"0roceedings, 3rd International Symposium on Methodologies for Intelligent Systems (ISMIS-88)","first-page":"485","article-title":"When is closed world reasoning tractable?","author":"Schlipf","year":"1988"},{"key":"10.1016\/S0022-0000(05)80004-2_bib35","series-title":"Proceedings, Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89)","first-page":"1140","article-title":"The tractability of path-based inheritance","author":"Selman","year":"1989"},{"key":"10.1016\/S0022-0000(05)80004-2_bib36","series-title":"Proceedings, Eighth National Conference on Artificial Intelligence (AAAI-90)","first-page":"571","article-title":"It's not my default: The complexity of membership problems in restricted propositional default logics","author":"Stillman","year":"1990"},{"key":"10.1016\/S0022-0000(05)80004-2_bib37","series-title":"Proceedings, Fourth Conference on Artificial Intelligence (AAAI-84)","first-page":"322","article-title":"Implicit ordering of defaults in inheritance systems","author":"Touretzky","year":"1984"},{"key":"10.1016\/S0022-0000(05)80004-2_bib38","series-title":"Proceedings, Fifth Conference on Principle of Database Systems (PODS-86)","article-title":"On the integrity of databases with incomplete information","author":"Vardi","year":"1986"},{"key":"10.1016\/S0022-0000(05)80004-2_bib39","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/0022-0000(86)90016-4","article-title":"Querying logical databases","volume":"33","author":"Vardi","year":"1986","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(05)80004-2_bib40","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00244994","article-title":"Deduction in non-Horn databases","volume":"1","author":"Yahya","year":"1985","journal-title":"J. Automated Reasoning"},{"key":"10.1016\/S0022-0000(05)80004-2_bib41","series-title":"Proceedings, Seventh National Conference on Artificial Intelligence (AAAI-88)","first-page":"460","article-title":"On reducing parallel circumscription","author":"Yuan","year":"1988"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000005800042?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000005800042?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,22]],"date-time":"2019-01-22T17:27:42Z","timestamp":1548178062000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000005800042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,4]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,4]]}},"alternative-id":["S0022000005800042"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(05)80004-2","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[1994,4]]}}}