{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T11:03:25Z","timestamp":1777892605492,"version":"3.51.4"},"reference-count":75,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1995,4,1]],"date-time":"1995-04-01T00:00:00Z","timestamp":796694400000},"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":6690,"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":[[1995,4]]},"DOI":"10.1016\/0004-3702(94)00009-p","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T02:00:28Z","timestamp":1027648828000},"page":"249-310","source":"Crossref","is-referenced-by-count":97,"title":["Tractable reasoning via approximation"],"prefix":"10.1016","volume":"74","author":[{"given":"Marco","family":"Schaerf","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Cadoli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0004-3702(94)00009-P_BIB1","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0743-1066(86)90013-0","article-title":"Login: a logic programming language with built-in inheritance","volume":"3","author":"A\u00eft-Kaci","year":"1986","journal-title":"J. Logic Program."},{"key":"10.1016\/0004-3702(94)00009-P_BIB2","author":"Anderson","year":"1975"},{"key":"10.1016\/0004-3702(94)00009-P_BIB3","series-title":"Proceedings International Conference on Database Theory (ICDT-88)","first-page":"19","article-title":"Data models and languages for databases","author":"Been","year":"1988"},{"key":"10.1016\/0004-3702(94)00009-P_BIB4","series-title":"Proceedings ACM SIGMOD International Conference on the Management of Data","first-page":"58","article-title":"CLASSIC: a structural data model for objects","author":"Borgida","year":"1989"},{"key":"10.1016\/0004-3702(94)00009-P_BIB5","series-title":"Proceedings Third International Conference on the Principles of Knowledge Representation and Reasoning (KR-92)","first-page":"247","article-title":"\u201cReducing\u201d CLASSIC to practice: knowledge representation theory meets reality","author":"Brachman","year":"1992"},{"key":"10.1016\/0004-3702(94)00009-P_BIB6","series-title":"Readings in Knowledge Representation","first-page":"41","article-title":"A fundamental tradeoff in knowledge representation and reasoning","author":"Brachman","year":"1985"},{"key":"10.1016\/0004-3702(94)00009-P_BIB7","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1207\/s15516709cog0902_1","article-title":"An overview of the KL-ONE knowledge representation system","volume":"9","author":"Brachman","year":"1985","journal-title":"Cogn. Sci."},{"key":"10.1016\/0004-3702(94)00009-P_BIB8","series-title":"Proceedings Second International Conference on the Principles of Knowledge Representation and Reasoning (KR-91)","first-page":"70","article-title":"The monotonic abduction problem: A functional characterization on the edge of tractability","author":"Bylander","year":"1991"},{"key":"10.1016\/0004-3702(94)00009-P_BIB9","series-title":"Proceedings IJCAI-93","first-page":"39","article-title":"Semantical and computational aspects of Horn approximations","author":"Cadoli","year":"1993"},{"key":"10.1016\/0004-3702(94)00009-P_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\/0004-3702(94)00009-P_BIB11","series-title":"Trends in Artificial Intelligence: Proceedings 2nd Conference of the Italian Association for Artificial Intelligence (AI\u2217IA-91)","first-page":"68","article-title":"Approximate entailment","volume":"549","author":"Cadoli","year":"1991"},{"key":"10.1016\/0004-3702(94)00009-P_BIB12","series-title":"Proceedings Fourth Conference on Theoretical Aspects of Reasoning about Knowledge (TARK-92)","first-page":"169","article-title":"Approximate reasoning and non-omniscient agents","author":"Cadoli","year":"1992"},{"key":"10.1016\/0004-3702(94)00009-P_BIB13","series-title":"Proceedings Third International Conference on the Principles of Knowledge Representation and Reasoning (KR-92)","first-page":"330","article-title":"Approximation in concept description languages","author":"Cadoli","year":"1992"},{"key":"10.1016\/0004-3702(94)00009-P_BIB14_1","unstructured":"M. Cadoli, M. Schaerf, Approximate inference in default reasoning and circumscription, Fund. Informaticae, (to appear)."},{"key":"10.1016\/0004-3702(94)00009-P_BIB14_2","series-title":"Proceedings Tenth European Conference on Artificial Intelligence (ECAI-92)","first-page":"319","author":"Cadoli","year":"1992"},{"key":"10.1016\/0004-3702(94)00009-P_BIB15_1","doi-asserted-by":"crossref","unstructured":"M. Cadoli, M. Schaerf, The complexity of entailment in propositional multivalued logics, Annals of Mathematics and Artificial Intelligence, (to appear).","DOI":"10.1007\/BF02136173"},{"key":"10.1016\/0004-3702(94)00009-P_BIB15_2","series-title":"Proceedings AAAI Spring Symposium Series Workshop on AI and NP-hard problems","first-page":"15","author":"Cadoli","year":"1993"},{"key":"10.1016\/0004-3702(94)00009-P_BIB16","author":"Chellas","year":"1980"},{"key":"10.1016\/0004-3702(94)00009-P_BIB17","series-title":"Proceedings Third ACM Symposium on Theory of Computing","first-page":"151","article-title":"The complexity of theorem-proving procedures","author":"Cook","year":"1971"},{"key":"10.1016\/0004-3702(94)00009-P_BIB18","series-title":"Proceedings Fourth ACM Symposium on Principles of Programming Languages (POPL-77)","first-page":"238","article-title":"Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints","author":"Cousot","year":"1977"},{"key":"10.1016\/0004-3702(94)00009-P_BIB19","series-title":"Proceedings First International Conference on the Principles of Knowledge Representation and Reasoning (KR-89)","first-page":"67","article-title":"Towards a theory of access limited reasoning","author":"Crawford","year":"1989"},{"key":"10.1016\/0004-3702(94)00009-P_BIB20","series-title":"Proceedings Tenth European Conference on Artificial Intelligence (ECAI-92)","first-page":"354","article-title":"Tractable instances of some hard deduction problems","author":"Dalal","year":"1992"},{"key":"10.1016\/0004-3702(94)00009-P_BIB21","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0020-0190(92)90081-6","article-title":"A hierarchy of tractable satisfiability problems","volume":"44","author":"Dalal","year":"1992","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/0004-3702(94)00009-P_BIB22","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","article-title":"A computing procedure for quantification theory","volume":"7","author":"Davis","year":"1960","journal-title":"J. ACM"},{"key":"10.1016\/0004-3702(94)00009-P_BIB23","series-title":"Proceedings AAAI-88","first-page":"49","article-title":"An analysts of time-dependent planning","author":"Dean","year":"1988"},{"key":"10.1016\/0004-3702(94)00009-P_BIB24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","article-title":"Network-based heuristics for constraint-satisfaction problems","volume":"34","author":"Dechter","year":"1988","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00009-P_BIB25","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0004-3702(92)90076-A","article-title":"The complexity of existential quantification in concept languages","volume":"53","author":"Donini","year":"1992","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00009-P_BIB26","series-title":"Proceedings Second International Conference on the Principles of Knowledge Representation and Reasoning (KR-91)","first-page":"151","article-title":"The complexity of concept languages","author":"Donini","year":"1991"},{"key":"10.1016\/0004-3702(94)00009-P_BIB27","series-title":"Proceedings IJCAI-91","first-page":"458","article-title":"Tractable concept languages","author":"Donini","year":"1991"},{"key":"10.1016\/0004-3702(94)00009-P_BIB28","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 Program."},{"key":"10.1016\/0004-3702(94)00009-P_BIB29","author":"Dreben","year":"1979"},{"key":"10.1016\/0004-3702(94)00009-P_BIB30","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/BF00373152","article-title":"Intuitive semantics for first-degree entailments and \u2018coupled trees\u2019","volume":"29","author":"Dunn","year":"1976","journal-title":"Philos. Stud."},{"key":"10.1016\/0004-3702(94)00009-P_BIB31","series-title":"Proceedings 10th Symposium on Theoretical Aspects of Computer Science","article-title":"The complexity of logic-based abduction","volume":"665","author":"Eiter","year":"1993"},{"key":"10.1016\/0004-3702(94)00009-P_BIB32","series-title":"Presented at the 4th International Workshop on Nonmonotonic Reasoning","article-title":"Towards efficient default reasoning","author":"Etherington","year":"1992"},{"key":"10.1016\/0004-3702(94)00009-P_BIB33","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0004-3702(87)90003-8","article-title":"Belief, awareness and limited reasoning","volume":"34","author":"Fagin","year":"1988","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00009-P_BIB34","series-title":"Proceedings Third Conference on Theoretical Aspects of Reasoning about Knowledge (TARK-90)","first-page":"41","article-title":"A nonstandard approach to the logical omniscience problem","author":"Fagin","year":"1990"},{"key":"10.1016\/0004-3702(94)00009-P_BIB35","series-title":"Proceedings IJCAI-85","first-page":"148","article-title":"Using model theory to specify AI programs","author":"Frisch","year":"1985"},{"key":"10.1016\/0004-3702(94)00009-P_BIB36","series-title":"Proceedings IJCAI-87","first-page":"515","article-title":"Inference without chaining","author":"Frisch","year":"1987"},{"key":"10.1016\/0004-3702(94)00009-P_BIB37","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0020-0190(88)90113-5","article-title":"Polynomially solvable satisfiability problems","volume":"29","author":"Gallo","year":"1988","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/0004-3702(94)00009-P_BIB38","article-title":"Anytime declarativism","author":"Ginsberg","year":"1991"},{"key":"10.1016\/0004-3702(94)00009-P_BIB39","series-title":"Proceedings Second International Conference on the Principles of Knowledge Representation and Reasoning (KR-91)","first-page":"250","article-title":"Computational considerations in reasoning about action","author":"Ginsberg","year":"1991"},{"key":"10.1016\/0004-3702(94)00009-P_BIB40","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/0004-3702(92)90021-O","article-title":"A theory of abstraction","volume":"57","author":"Giunchiglia","year":"1992","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00009-P_BIB41","series-title":"Proceedings Third International Conference on the Principles of Knowledge Representation and Reasoning (KR-92)","first-page":"383","article-title":"Learning useful Horn approximations","author":"Greiner","year":"1992"},{"key":"10.1016\/0004-3702(94)00009-P_BIB42","article-title":"Reasoning about knowledge: a survey circa 1991","author":"Halpern","year":"1991"},{"key":"10.1016\/0004-3702(94)00009-P_BIB43","author":"Hintikka","year":"1962"},{"key":"10.1016\/0004-3702(94)00009-P_BIB44","series-title":"Proceedings IJCAI-87","first-page":"997","article-title":"Domain abstraction and limited reasoning","author":"Imielinski","year":"1987"},{"key":"10.1016\/0004-3702(94)00009-P_BIB45","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1109\/MC.1983.1654195","article-title":"The role of logic in knowledge representation","volume":"16","author":"Israel","year":"1983","journal-title":"IEEE Computer"},{"key":"10.1016\/0004-3702(94)00009-P_BIB46","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF01531077","article-title":"Solving propositional satisfiability problems","volume":"1","author":"Jeroslow","year":"1990","journal-title":"Ann. Math. Artif. Intell."},{"key":"10.1016\/0004-3702(94)00009-P_BIB47","series-title":"Proceedings of International Workshop on Processing Declarative Knowledge (PDK-91)","first-page":"287","article-title":"A general framework for knowledge compilation","volume":"567","author":"Kautz","year":"1991"},{"key":"10.1016\/0004-3702(94)00009-P_BIB48","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\/0004-3702(94)00009-P_BIB49","series-title":"Proceedings AAAI-92","first-page":"786","article-title":"Forming concepts for fast inference","author":"Kautz","year":"1992"},{"key":"10.1016\/0004-3702(94)00009-P_BIB50","author":"Kleene","year":"1966"},{"key":"10.1016\/0004-3702(94)00009-P_BIB51","first-page":"83","article-title":"Semantical considerations on modal logic","volume":"16","author":"Kripke","year":"1963","journal-title":"Acta Philos. Fenn."},{"key":"10.1016\/0004-3702(94)00009-P_BIB52","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1137\/0206033","article-title":"The computational complexity of provability in systems of modal propositional logic","volume":"6","author":"Ladner","year":"1977","journal-title":"SIAM J. Computing"},{"key":"10.1016\/0004-3702(94)00009-P_BIB53","series-title":"Proceedings IJCAI-87","first-page":"402","article-title":"Tractable meta-reasoning in propositional logics of belief","author":"Lakemeyer","year":"1987"},{"key":"10.1016\/0004-3702(94)00009-P_BIB54","series-title":"Proceedings AAAI-84","first-page":"198","article-title":"A logic of implicit and explicit belief","author":"Levesque","year":"1984"},{"key":"10.1016\/0004-3702(94)00009-P_BIB55","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/BF00297511","article-title":"Logic and the complexity of reasoning","volume":"17","author":"Levesque","year":"1988","journal-title":"J. Philos. Logic"},{"key":"10.1016\/0004-3702(94)00009-P_BIB56","series-title":"Proceedings IJCAI-89","first-page":"1061","article-title":"A knowledge-level account of abduction","author":"Levesque","year":"1989"},{"key":"10.1016\/0004-3702(94)00009-P_BIB57","author":"Loveland","year":"1978"},{"key":"10.1016\/0004-3702(94)00009-P_BIB58","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1145\/122296.122309","article-title":"Inside the LOOM desscription classifier","volume":"2","author":"MacGregor","year":"1991","journal-title":"SIGART Bull."},{"key":"10.1016\/0004-3702(94)00009-P_BIB59","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0004-3702(90)90087-G","article-title":"Terminological reasoning is inherently intractable","volume":"43","author":"Nebel","year":"1990","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00009-P_BIB60","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0004-3702(91)90049-P","article-title":"Logic and artificial intelligence","volume":"47","author":"Nilsson","year":"1991","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00009-P_BIB61","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0004-3702(89)90036-2","article-title":"A four-valued semantics for terminological logic","volume":"38","author":"Patel-Schneider","year":"1989","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00009-P_BIB62","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF00244354","article-title":"A decidable first-order logic for knowledge representation","volume":"6","author":"Patel-Schneider","year":"1990","journal-title":"J. Automated Reason."},{"key":"10.1016\/0004-3702(94)00009-P_BIB63","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1145\/321250.321253","article-title":"A machine oriented logic based on the resolution principle","volume":"12","author":"Robinson","year":"1965","journal-title":"J. ACM"},{"key":"10.1016\/0004-3702(94)00009-P_BIB64","author":"Rogers","year":"1967"},{"key":"10.1016\/0004-3702(94)00009-P_BIB65","series-title":"Proceedings IJCAI-91","first-page":"212","article-title":"Composing real-time systems","author":"Russell","year":"1991"},{"key":"10.1016\/0004-3702(94)00009-P_BIB66","series-title":"Proceedings 10th ACM Symposium on Theory of Computing","first-page":"216","article-title":"The complexity of satisfiability problems","author":"Schaefer","year":"1978"},{"key":"10.1016\/0004-3702(94)00009-P_BIB67","series-title":"Proceedings IJCAI-91","first-page":"466","article-title":"A correspondence theory for terminological logics: preliminary report","author":"Schild","year":"1991"},{"issue":"1","key":"10.1016\/0004-3702(94)00009-P_BIB68","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(91)90078-X","article-title":"Attributive concept descriptions with complements","volume":"48","author":"Schmidt-Schau\u03b2","year":"1991","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00009-P_BIB69","series-title":"Proceedings AAAI-91","article-title":"Knowledge compilation using Horn approximations","author":"Selman","year":"1991"},{"key":"10.1016\/0004-3702(94)00009-P_BIB70","series-title":"Proceedings IJCAI-89","article-title":"The tractability of path-based inheritance","author":"Selman","year":"1989"},{"key":"10.1016\/0004-3702(94)00009-P_BIB71","series-title":"Proceedings AAAI-90","article-title":"It's not my default: The complexity of membership problems in restricted propositional default logics","author":"Stillman","year":"1990"},{"issue":"1","key":"10.1016\/0004-3702(94)00009-P_BIB72","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(88)90014-4","article-title":"A satisfiability tester for non-clausal propositional calculus","volume":"79","author":"Van Gelder","year":"1988","journal-title":"Inf. Comput."},{"key":"10.1016\/0004-3702(94)00009-P_BIB73","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. Syst. Sci."}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:000437029400009P?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:000437029400009P?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T04:50:07Z","timestamp":1555303807000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/000437029400009P"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,4]]},"references-count":75,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,4]]}},"alternative-id":["000437029400009P"],"URL":"https:\/\/doi.org\/10.1016\/0004-3702(94)00009-p","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[1995,4]]}}}