{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:13:45Z","timestamp":1725455625082},"publisher-location":"Berlin\/Heidelberg","reference-count":28,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540537090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0020813","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:07:52Z","timestamp":1131862072000},"page":"372-383","source":"Crossref","is-referenced-by-count":2,"title":["Complexity classification of Truth Maintenance systems"],"prefix":"10.1007","author":[{"given":"Vladislav","family":"Rutenburg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Cook, S.A., \"The Complexity of Theorem-Proving Procedures\", Proceedings of the 3rd ACM STOC, 1971, 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"31_CR2","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0004-3702(79)90008-0","volume":"12","author":"J. Doyle","year":"1979","unstructured":"Doyle, J., (1979), \"A Truth Maintenance System,\" Artificial Intelligence 12, 231\u2013272.","journal-title":"Artificial Intelligence"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0004-3702(86)90080-9","volume":"28","author":"J. Kleer de","year":"1986","unstructured":"de Kleer, J., (1986), \"An Assumption-based Truth Maintenance System,\" Artificial Intelligence, 28: 127\u2013162.","journal-title":"Artificial Intelligence"},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0004-3702(86)90082-2","volume":"28","author":"J. Kleer de","year":"1986","unstructured":"de Kleer, J., (1986), \"Problem Solving with the ATMS,\" Artificial Intelligence 28, 197\u2013224","journal-title":"Artificial Intelligence"},{"key":"31_CR5","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0004-3702(86)90081-0","volume":"28","author":"J. Kleer de","year":"1986","unstructured":"de Kleer, J., (1986), \"Extending the ATMS,\" Artificial Intelligence 28, 163\u2013196.","journal-title":"Artificial Intelligence"},{"key":"31_CR6","unstructured":"de Kleer, J., (1988), \"A General Labelling Algorithm for ATMS,\" Proc. 7th AAAI, St.Paul, MN."},{"key":"31_CR7","unstructured":"de Kleer, J., Doyle, J., Rich C., Steele, G., Sussman, G.J., [1978] \"AMORD: a Deductive Procedure System\", MIT Artificial Intelligence Lab Memo 435."},{"key":"31_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"Davis, M. and H. Putnam, \"A Computing Procedure for Quantification Theory,\" Journal of ACM 7, 1960, 201\u2013215.","journal-title":"Journal of ACM"},{"key":"31_CR9","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R. and D. S. Johnson, \"Computers and Intractability. A Guide to the Theory of NP-Completeness\", Freeman, San Francisco, 1979."},{"key":"31_CR10","doi-asserted-by":"crossref","unstructured":"Garey, M., D. Johnson, L. J. Stockmeyer. \"Some Simplified NP-Complete Graph Problems\", Theor. Computer Sci. (1976)","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Hastad, J., (1986), \"Computational Limitations for Small Depth Circuits,\" MIT Press.","DOI":"10.1145\/12130.12132"},{"key":"31_CR12","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":"Karp, R. M. \"Reducibility among Combinatorial Problems\", in Complexity of Computer Computations, Plenum, New York, 1972, 85\u2013103."},{"key":"31_CR13","unstructured":"McAllester, D., (1982), \"Reasoning Utility Package User's Manual,\" MIT Artificial Intelligence Lab Memo 667."},{"key":"31_CR14","unstructured":"McAllester, D., (1985), \"A Widely Used Truth Maintenance System,\" Unpubl."},{"key":"31_CR15","unstructured":"McAllester, D., (1988), \"Ontic: A Knowledge Representation System for Mathematics,\" MIT Press."},{"key":"31_CR16","doi-asserted-by":"crossref","unstructured":"McDermott, D., (1983), \"Contexts and Data Dependencies: a Synthesis,\" IEEE Transactions on Pattern Analysis and Machine Intelligenc, 5(3).","DOI":"10.1109\/TPAMI.1983.4767388"},{"key":"31_CR17","unstructured":"McAllester, D. and McDermott, D. \"AAAI 88 Truth Maintenance Systems\", tutorial."},{"key":"31_CR18","unstructured":"Martins, J.P. and Shapiro, S.C. (1983), \"Reasoning in Multiple Belief Systems,\" Proc. 8th IJCAI, Karlsruhe, FRG."},{"key":"31_CR19","unstructured":"Provan, G., (1987), \"Efficiency Analysis of Multiple-Context TMSs in Scene Representation,\" Proc. 6th AAAI, Seattle, WA."},{"key":"31_CR20","unstructured":"Rutenburg, V., (1988), \"Complexity of Generalized Graph Coloring Problems,\" Doctoral Thesis, Stanford University, June '88."},{"key":"31_CR21","volume-title":"Computational Complexity of Truth Maintenance","author":"V. Rutenburg","year":"1988","unstructured":"Rutenburg, V., (1988), \"Computational Complexity of Truth Maintenance,\" Rockwell International Science Center, Palo Alto, Ca, November 1988."},{"key":"31_CR22","unstructured":"Reiter, R. and de Kleer, J. (1987), \"Foundations of Assumption-based Truth Maintenance Systems,\" Proc. 6th AAAI, Seattle."},{"key":"31_CR23","unstructured":"Williams, C., (1984), \"ART the Advanced Reasoning Tool \u2014 Conceptual Overview,\" Inference Corp."},{"key":"31_CR24","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0004-3702(77)90029-7","volume":"9","author":"R. Stallman","year":"1977","unstructured":"Stallman, R. and Sussman, G.J., (1977), \"Forward Reasoning and DDB in a System for Computer-Aided Circuit Analysis,\" Artificial Intelligence 9, 135\u2013196","journal-title":"Artificial Intelligence"},{"key":"31_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L. J. \"Polynomial-time Hierarchy\", Theoretical Computer Science 3 (1977), 1\u201322.","journal-title":"Theoretical Computer Science"},{"key":"31_CR26","unstructured":"Zabih, R., [1987], \"Another Look at Truth Maintenance\", unpublished."},{"key":"31_CR27","doi-asserted-by":"crossref","unstructured":"Yao, A.C., \"Separating the Polynomial-Time Hierarchy by Oracles\", Proceedings of the 26th IEEE FOCS, 1985, 1\u201310.","DOI":"10.1109\/SFCS.1985.49"},{"key":"31_CR28","doi-asserted-by":"crossref","unstructured":"Yannakakis, M., \"Node-and Edge-Deletion NP-complete Problems\", Proceedings of the 10th ACM STOC, 1978, 253\u2013264.","DOI":"10.1145\/800133.804355"}],"container-title":["Lecture Notes in Computer Science","STACS 91"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0020813.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:45:09Z","timestamp":1607550309000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0020813"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540537090"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/bfb0020813","relation":{},"subject":[]}}