{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,4]],"date-time":"2026-08-04T22:40:49Z","timestamp":1785883249701,"version":"3.56.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"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":[[1994,9]]},"DOI":"10.1007\/bf01530952","type":"journal-article","created":{"date-parts":[[2005,4,19]],"date-time":"2005-04-19T00:29:48Z","timestamp":1113870588000},"page":"207-231","source":"Crossref","is-referenced-by-count":18,"title":["Propositional truth maintenance systems: Classification and complexity analysis"],"prefix":"10.1007","volume":"10","author":[{"given":"Vladislav","family":"Rutenburg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"S.A. Cook, The complexity of theorem-proving procedures,Proc. 3rd ACM STOC (1971) pp. 151?158.","DOI":"10.1145\/800157.805047"},{"key":"CR2","unstructured":"M. Cadoli and M. Schaerf, A survey on complexity results for non-monotonic logics, Dipartamento di Informatica e Sistemistica, University of Rome ?La Sapienza? (1992) unpublished manuscript."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0004-3702(79)90008-0","volume":"12","author":"J. Doyle","year":"1979","unstructured":"J. Doyle, A truth maintenance system, Artificial Intelligence 12 (1979) 231?272.","journal-title":"Artificial Intelligence"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0004-3702(86)90080-9","volume":"28","author":"J. Kleer de","year":"1986","unstructured":"J. de Kleer, An assumption-based truth maintenance system, Artificial Intelligence 28 (1986) 127?162.","journal-title":"Artificial Intelligence"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0004-3702(86)90082-2","volume":"28","author":"J. Kleer de","year":"1986","unstructured":"J. de Kleer, Problem solving with the ATMS, Artificial Intelligence 28 (1986) 197?224.","journal-title":"Artificial Intelligence"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0004-3702(86)90081-0","volume":"28","author":"J. Kleer de","year":"1986","unstructured":"J. de Kleer, Extending the ATMS, Artificial Intelligence 28 (1986) 163?196.","journal-title":"Artificial Intelligence"},{"key":"CR7","unstructured":"J. de Kleer, A general labelling algorithm for ATMS,Proc. 7th AAAI, St. Paul, Minnesota (1988)."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"M. Davis, and H. Putnam, A computing procedure for quantification theory, J. ACM 7 (1960) 201?215.","journal-title":"J. ACM"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0004-3702(90)90086-F","volume":"43","author":"C. Elkan","year":"1990","unstructured":"C. Elkan, A rational reconstruction of nonmonotonic truth maintenance systems, Artificial Intelligence 43 (1990) 219?234.","journal-title":"Artificial Intelligence"},{"key":"CR10","volume-title":"CD-TR 91\/23","author":"T. Eiter","year":"1991","unstructured":"T. Eiter and G. Gottlob, On the complexity of propositional knowledge base revision, Updates, and Counterfactuals, Technische Universitaet, Vienna, CD-TR 91\/23 (July 1991)."},{"key":"CR11","volume-title":"CD-TR 91\/24","author":"G. Gottlob","year":"1991","unstructured":"G. Gottlob, Complexity results for nonmonotonic logic, Technische Universit\u00e4t, Vienna, CD-TR 91\/24 (August 1991)."},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"M. Garey, D. Johnson and L.J. Stockmeyer, Some simplified NP-complete graph problems, Theor. Comp. Sci. (1976).","DOI":"10.1145\/800113.803626"},{"key":"CR13","unstructured":"J. Hastad,Computational Limitations for Small Depth Circuits (MIT Press, 1986)."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, Reducibility among combinatorial problems, in:Complexity of Computer Computations (Plenum, New York, 1972) pp. 85?103."},{"key":"CR15","unstructured":"J.P. Martins and S.C. Shapiro, Reasoning in multiple belief systems,Proc. 8th IJCAI, Karlsruhe (1983)."},{"key":"CR16","unstructured":"D. McAllester, Reasoning utility package user's manual, MIT Artificial Intelligence Lab Memo 667 (1982)."},{"key":"CR17","unstructured":"D. McAllester, A widely used truth maintenance system, (1985) unpublished."},{"key":"CR18","unstructured":"D. McAllester and D. McDermott, AAAI 88 truth maintenance systems, tutorial (1988)."},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"D. McDermott, Contexts and data dependencies: a synthesis, IEEE Trans. Pattern Anal. Machine Intellig. 5(3) (1983).","DOI":"10.1109\/TPAMI.1983.4767388"},{"key":"CR20","unstructured":"G. Provan, Efficiency analysis of multiple-context TMSs in scene representation,Proc. 6th AAAI, Seattle, Washington (1987)."},{"key":"CR21","unstructured":"G. Provan, The computational complexity of multiple context truth maintenance systems,ECAI '90 (1990) pp. 522?527."},{"key":"CR22","unstructured":"V. Rutenburg, Complexity of generalized graph coloring problems, Doctoral Thesis, Stanford University (June 1988)."},{"key":"CR23","volume-title":"Computational complexity of truth maintenance","author":"V. Rutenburg","year":"1988","unstructured":"V. Rutenburg, Computational complexity of truth maintenance, Rockwell International Science Center, Palo Alto, California (November 1988)."},{"key":"CR24","unstructured":"V. Rutenburg, Computational complexity of truth maintenance systems,8th Symp. on Theoretical Aspects of Computer Science, Springer-Verlag Lecture Notes in Computer Science 480, eds. Choffrut and Jantsen (1991)."},{"key":"CR25","unstructured":"R. Reiter and J. de Kleer, Foundations of assumption-based truth maintenance systems,Proc. 6th AAAI, Seattle, Washington (1987)."},{"key":"CR26","unstructured":"B. Selman and H. Levesque, Abductive and default reasoning: a computational core,Proc. 8th AAAI, Boston, Massachusetts (1990)."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0004-3702(77)90029-7","volume":"9","author":"R. Stallman","year":"1977","unstructured":"R. Stallman and G.J. Sussman, Forward reasoning and DDB in a system for computer-aided circuit analysis, Artificial Intelligence 9 (1977) 135?196.","journal-title":"Artificial Intelligence"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1977","unstructured":"L.J. Stockmeyer, Polynomial-time hierarchy, Theor. Comp. Sci. 3 (1977) 1?22.","journal-title":"Theor. Comp. Sci."},{"key":"CR29","unstructured":"C. Williams, ART the advanced reasoning tool ? Conceptual overview, Inference Corp. (1984)."},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, Node- and edge-deletion NP-complete problems,Proc. 10th ACM STOC (1978) pp. 253?264.","DOI":"10.1145\/800133.804355"},{"key":"CR31","doi-asserted-by":"crossref","unstructured":"A.C. Yao, Separating the polynomial-time hierarchy by oracles,Proc. 26th IEEE FOCS (1985) pp. 1?10.","DOI":"10.1109\/SFCS.1985.49"},{"key":"CR32","unstructured":"R. Zabih, Another look at truth maintenance, (1987) unpublished."},{"key":"CR33","unstructured":"J. de Kleer, J. Doyle, C. Rich, G. Steele and G.J. Sussman, AMORD: a deductive procedure system, MIT Artificial Intelligence Lab Memo 435 (1978)."},{"key":"CR34","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 (Freeman, San Francisco, 1979)."}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01530952\/fulltext.html","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01530952.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01530952\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01530952","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T00:01:27Z","timestamp":1586217687000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01530952"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["BF01530952"],"URL":"https:\/\/doi.org\/10.1007\/bf01530952","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}