{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:04Z","timestamp":1761611164002},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,3,1]],"date-time":"1996-03-01T00:00:00Z","timestamp":825638400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[1996,3]]},"DOI":"10.1007\/bf02136173","type":"journal-article","created":{"date-parts":[[2005,9,15]],"date-time":"2005-09-15T06:55:58Z","timestamp":1126767358000},"page":"29-50","source":"Crossref","is-referenced-by-count":31,"title":["On the complexity of entailment in propositional multivalued logics"],"prefix":"10.1007","volume":"18","author":[{"given":"Marco","family":"Cadoli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Schaerf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02136173_CR1","volume-title":"Entailment: The Logic of Relevance and Necessity","author":"A. Anderson","year":"1975","unstructured":"A. Anderson and N. Belnap,Entailment: The Logic of Relevance and Necessity (Princeton University Press, Princeton, NJ, 1975)."},{"key":"BF02136173_CR2","first-page":"8","volume-title":"Modern Uses of Many-Valued Logics","author":"N. Belnap","year":"1977","unstructured":"N. Belnap, A useful four-valued logic, in:Modern Uses of Many-Valued Logics, eds. G. Eppstein and J. Dunn (Reidel, Dordrecht, Netherlands, 1977) pp. 8\u201337."},{"key":"BF02136173_CR3","volume-title":"Handbook of Theoretical Computer Science","author":"R. Boppana","year":"1990","unstructured":"R. Boppana and M. Sipser, The complexity of finite functions, in:Handbook of Theoretical Computer Science, ed. J. van Leeuwen. Vol. A, Chapter 14 (Elsevier Science Publishers B.V., North-Holland, 1990)."},{"key":"BF02136173_CR4","unstructured":"M. Cadoli and M. Schaerf, Approximate inference in default reasoning and circumscription, in:Proceedings of the Tenth European Conference on Artificial Intelligence (ECAI-92) (August 1992) pp. 319\u2013323. Full version appears inFundamenta Informaticae 23 (1995) 123\u2013143."},{"key":"BF02136173_CR5","unstructured":"M. Cadoli and M. Schaerf, Approximate reasoning and non-omniscient agents, in:Proceedings of the Fourth Conference on Theoretical Aspects of Reasoning about Knowledge (TARK-92) (1992) pp. 169\u2013183. Full version appears inArtificial Intelligence Journal 74 (1995) 249\u2013310."},{"key":"BF02136173_CR6","unstructured":"M. Cadoli and M. Schaerf, Approximation in concept description languages, in:Proceedings of the Third International Conference on the Principles of Knowledge Representation and Reasoning (KR-92), eds. B. Nebel, C. Rich and W. Swartout (October 1992) pp. 330\u2013341."},{"key":"BF02136173_CR7","doi-asserted-by":"crossref","unstructured":"S.A. Cook, The complexity of theorem-proving procedures, in:Proceedings of the 3rd ACM Symposium on Theory Of Computing (STOC-71) (1971) pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"BF02136173_CR8","unstructured":"M. Dalal, Efficient propositional constraint propagation, in:Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92) (1992) pp. 409\u2013414."},{"key":"BF02136173_CR9","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"1","author":"W.P. Dowling","year":"1984","unstructured":"W.P. Dowling and J.H. Gallier, Linear-time algorithms for testing the satisfiability of propositional Horn formulae,Journal of Logic Programming 1 (1984) 267\u2013284.","journal-title":"Journal of Logic Programming"},{"key":"BF02136173_CR10","unstructured":"R. Fagin, J.Y. Halpern and M.Y. Vardi, A nonstandard approach to the logical omniscience problem, in:Proceedings of the Third Conference on Theoretical Aspects of Reasoning about Knowledge (TARK-90) (1990) pp. 41\u201355."},{"key":"BF02136173_CR11","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/S0743-1066(85)80005-4","volume":"2","author":"M. Fitting","year":"1985","unstructured":"M. Fitting, A Kripke-Kleene semantics for logic programs,Journal of Logic Programming 2 (1985) 295\u2013312.","journal-title":"Journal of Logic Programming"},{"key":"BF02136173_CR12","unstructured":"A.M. Frisch, Using model theory to specify AI programs, in:Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI-85) (1985) pp. 148\u2013154."},{"key":"BF02136173_CR13","unstructured":"A.M. Frisch, Inference without chaining, in:Proceedings of the Tenth International Joint Conference on Artificial Intelligence (IJCAI-87) (1987) pp. 515\u2013519."},{"key":"BF02136173_CR14","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson,Computers and Intractability, A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco, CA, 1979)."},{"key":"BF02136173_CR15","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1111\/j.1467-8640.1988.tb00280.x","volume":"4","author":"M.L. Ginsberg","year":"1988","unstructured":"M.L. Ginsberg, Multivalued logics: A uniform approach to reasoning in artificial intelligence,Computational Intelligence 4 (1988) 265\u2013316.","journal-title":"Computational Intelligence"},{"key":"BF02136173_CR16","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1007\/BF00558761","volume":"4","author":"J. Hintikka","year":"1975","unstructured":"J. Hintikka, Impossible possible worlds vindicated,Journal of Philosophical Logic 4 (1975) 475\u2013484.","journal-title":"Journal of Philosophical Logic"},{"key":"BF02136173_CR17","volume-title":"Fundamentals of Data Strctures","author":"E. Horowitz","year":"1976","unstructured":"E. Horowitz and S. Sahni,Fundamentals of Data Strctures (Pitman, London, 1976)."},{"issue":"2","key":"BF02136173_CR18","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF00245460","volume":"9","author":"M. Kifer","year":"1992","unstructured":"M. Kifer and E.L. Lozinskii, A logic for reasoning with inconsistency,Journal of Automated Reasoning 9(2) (November 1992) 179\u2013215.","journal-title":"Journal of Automated Reasoning"},{"key":"BF02136173_CR19","unstructured":"G. Lakemeyer, Tractable meta-reasoning in propositional logics of belief, in:Proceedings of the Tenth International Joint Conference on Artificial Intelligence (IJCAI-87) (1987) pp. 402\u2013408."},{"key":"BF02136173_CR20","unstructured":"H.J. Levesque, A logic of implicit and explicit belief, in:Proceedings of the Fourth National Conference on Artificial Intelligence (AAAI-84) (1984) pp. 198\u2013202."},{"key":"BF02136173_CR21","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/BF00297511","volume":"17","author":"H.J. Levesque","year":"1988","unstructured":"H.J. Levesque, Logic and the complexity of reasoning,Journal of Philosophical Logic 17 (1988) 355\u2013389.","journal-title":"Journal of Philosophical Logic"},{"key":"BF02136173_CR22","unstructured":"H.J. Levesque, A knowledge-level account of abduction, in:Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89) (1989) pp. 1061\u20131067."},{"key":"BF02136173_CR23","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0004-3702(89)90036-2","volume":"38","author":"P.F. Patel-Schneider","year":"1989","unstructured":"P.F. Patel-Schneider, A four-valued semantics for terminological logic,Artificial Intelligence Journal 38 (1989) 319\u2013351.","journal-title":"Artificial Intelligence Journal"},{"key":"BF02136173_CR24","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF00244354","volume":"6","author":"P.F. Patel-Schneider","year":"1990","unstructured":"P.F. Patel-Schneider, A decidable first-order logic for knowledge representation,Journal of Automated Reasoning 6 (1990) 361\u2013388.","journal-title":"Journal of Automated Reasoning"},{"key":"BF02136173_CR25","unstructured":"T. Przymusinski, Three-valued formalizations of non-monotonic reasoning and logic programming, in:Proceedings of the First International Conference on the Principles of Knowledge Representation and Reasoning (KR-89) (1989) pp. 341\u2013348."},{"key":"BF02136173_CR26","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1145\/116825.116838","volume":"38","author":"A. Gelder van","year":"1991","unstructured":"A. van Gelder, K.A. Ross and J.S. Schlipf, The well-founded semantics for general logic programs,Journal of the ACM 38 (1991) 620\u2013650.","journal-title":"Journal of the ACM"},{"key":"BF02136173_CR27","unstructured":"M.Y. Vardi, The complexity of relational query languages, in:Proceedings of the 14th ACM Symposyum on Theory Of Computing (STOC-82) (1982) pp. 137\u2013146."}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02136173.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02136173\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02136173","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T09:22:47Z","timestamp":1557825767000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02136173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,3]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,3]]}},"alternative-id":["BF02136173"],"URL":"https:\/\/doi.org\/10.1007\/bf02136173","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,3]]}}}