{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T01:52:19Z","timestamp":1750125139399},"reference-count":54,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1996,12,1]],"date-time":"1996-12-01T00:00:00Z","timestamp":849398400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T00:00:00Z","timestamp":1374710400000},"content-version":"vor","delay-in-days":6080,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[1996,12]]},"DOI":"10.1016\/s0004-3702(96)00009-4","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T00:24:09Z","timestamp":1027643049000},"page":"215-251","source":"Crossref","is-referenced-by-count":24,"title":["Is intractability of nonmonotonic reasoning a real drawback?"],"prefix":"10.1016","volume":"88","author":[{"given":"Marco","family":"Cadoli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco M.","family":"Donini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Schaerf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0004-3702(96)00009-4_BIB1","series-title":"Proceedings Third International Conference on the Principles of Knowledge Representation and Reasoning","first-page":"306","article-title":"Embedding defaults into terminological knowledge representation formalisms","author":"Baader","year":"1992"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB2","series-title":"Proceedings First International Conference on the Principles of Knowledge Representation and Reasoning","first-page":"33","article-title":"Hierarchical knowledge bases and efficient disjunctive reasoning","author":"Borgida","year":"1989"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB3","series-title":"Proceedings AAAI-90","first-page":"1082","article-title":"The future of knowledge representation","author":"Brachman","year":"1990"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB4","series-title":"Proceedings of the Fourth Italian Conference on Theoretical Computer Science","first-page":"125","article-title":"On the complexity of model finding for nonmonotonic propositional logics","author":"Cadoli","year":"1992"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB5","series-title":"Proceedings IJCAI-93","first-page":"39","article-title":"Semantical and computational aspects of Horn approximations","author":"Cadoli","year":"1993"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB6","series-title":"Proceedings Fourteenth ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems","first-page":"151","article-title":"The size of a revised knowledge base","author":"Cadoli","year":"1995"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB7_1","series-title":"Proceedings AAAI-94","first-page":"946","article-title":"Is intractability of non-monotonic reasoning a real drawback?","author":"Cadoli","year":"1994"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB7_2","author":"Cadoli","year":"1995"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB8_1","series-title":"Proceedings Twelfth Symposium on Theoretical Aspects of Computer Science","first-page":"205","article-title":"On compact representations of propositional circumscription","author":"Cadoli","year":"1995"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB8_2","author":"Cadoli","year":"1995"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB9","unstructured":"also: Theoret. Comput. Sci. (to appear)."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB10","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0022-0000(05)80004-2","article-title":"The complexity of propositional closed world reasoning and circumscription","volume":"48","author":"Cadoli","year":"1994","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB11","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0743-1066(93)90029-G","article-title":"A survey of complexity results for non-monotonic logics","volume":"17","author":"Cadoli","year":"1993","journal-title":"J. Logic Programming"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB12","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\/S0004-3702(96)00009-4_BIB13","series-title":"Proceedings IJCAI-87","first-page":"489","article-title":"Relating default logic and circumscription","author":"Etherington","year":"1987"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB14","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\/S0004-3702(96)00009-4_BIB15","author":"Garey","year":"1979"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB16","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."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB17","doi-asserted-by":"crossref","first-page":"75","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."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB18","series-title":"Proceedings IJCAI-95","first-page":"862","article-title":"The comparative linguistics of knowledge representation","author":"Gogic","year":"1995"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB19","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1093\/logcom\/2.3.397","article-title":"Complexity results for nonmonotonic logics","volume":"2","author":"Gottlob","year":"1992","journal-title":"J. Logic Comput."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB20","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01530927","article-title":"Incomplete deductive databases","volume":"3","author":"Imielinski","year":"1991","journal-title":"Ann. Math. Artif. Intell."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB21","article-title":"A catalog of complexity classes","volume":"Vol. A","author":"Johnson","year":"1990"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB22","series-title":"Proceedings Twelfth ACM Symposium on Theory of Computing","first-page":"302","article-title":"Some connections between non-uniform and uniform complexity classes","author":"Karp","year":"1980"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB23","series-title":"Proceedings AAAI-93","first-page":"34","article-title":"Reasoning with characteristic models","author":"Kautz","year":"1993"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB24","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."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB25","series-title":"Proceedings AAAI-92","first-page":"786","article-title":"Forming concepts for fast inference","author":"Kautz","year":"1992"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB26_1","series-title":"Proceedings AAAI-94","first-page":"682","article-title":"Learning to reason","author":"Khardon","year":"1994"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB26_2","author":"Khardon","year":"1994"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB27_1","series-title":"Proceedings AAAI-94","first-page":"1148","article-title":"Reasoning with models","author":"Khardon","year":"1994"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB27_2","author":"Khardon","year":"1994"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB27_3","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/S0004-3702(96)00006-9","volume":"87","author":"Khardon","year":"1996","journal-title":"Artif. Intell."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB28","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0004-3702(84)90009-2","article-title":"Foundations of a functional approach to knowledge representation","volume":"23","author":"Levesque","year":"1984","journal-title":"Artif. Intell."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB29","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."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB30","series-title":"Proceedings IJCAI-85","first-page":"121","article-title":"Computing circumscription","author":"Lifschitz","year":"1985"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB31","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."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB32","series-title":"Proceedings Sixth Conference on Automated Deduction","first-page":"292","article-title":"On indefinite databases and the closed world assumption","author":"Minker","year":"1982"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB33","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0004-3702(95)00015-1","article-title":"Off-line reasoning for on-line efficiency","volume":"83","author":"Moses","year":"1996","journal-title":"Artif. Intell."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB34","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1006\/inco.1995.1005","article-title":"Computing circumscriptive databases I: theory and algorithms","volume":"116","author":"Nerode","year":"1995","journal-title":"Inform. Comput."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB35","author":"Papadimitriou","year":"1994"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB36","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. Autom. Reasoning"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB37","series-title":"Logic and Data Bases","first-page":"119","article-title":"On closed world data bases","author":"Reiter","year":"1978"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB38","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."},{"key":"10.1016\/S0004-3702(96)00009-4_BIB39","series-title":"Proceedings AAAI-82","first-page":"418","article-title":"Circumscription implies predicate completion (sometimes)","author":"Reiter","year":"1982"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB40","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0168-0072(87)90062-5","article-title":"Decidability and definability with circumscription","volume":"35","author":"Schlipf","year":"1987","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB41","series-title":"Proceedings Fourth International Conference on Principles of Knowledge Representation and Reasoning","first-page":"521","article-title":"Near-optimal plans, tractability, and reactivity","author":"Selman","year":"1994"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB42","series-title":"Proceedings AAAI-91","first-page":"904","article-title":"Knowledge compilation using Horn approximations","author":"Selman","year":"1991"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB43","author":"Sterling","year":"1986"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB44","series-title":"Proceedings 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\/S0004-3702(96)00009-4_BIB45","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1145\/116825.116838","article-title":"The well-founded semantics for general logic programs","volume":"38","author":"van Gelder","year":"1991","journal-title":"J. ACM"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB46","series-title":"Proceedings Fourteenth ACM Symposium on Theory of Computing","first-page":"137","article-title":"The complexity of relational query languages","author":"Vardi","year":"1982"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB47","series-title":"Proceedings Fourteenth ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems","article-title":"On the complexity of bounded-variable queries","author":"Vardi","year":"1995"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB48","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. Autom. Reasoning"},{"key":"10.1016\/S0004-3702(96)00009-4_BIB49","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","article-title":"Some consequences of non-uniform conditions on uniform classes","volume":"26","author":"Yap","year":"1983","journal-title":"Theoret. Comput. Sci."}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370296000094?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370296000094?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T06:28:16Z","timestamp":1555050496000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0004370296000094"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":54,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["S0004370296000094"],"URL":"https:\/\/doi.org\/10.1016\/s0004-3702(96)00009-4","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}