{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:17:02Z","timestamp":1725488222085},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540644064"},{"type":"electronic","value":"9783540697787"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-69778-0_19","type":"book-chapter","created":{"date-parts":[[2007,8,4]],"date-time":"2007-08-04T09:02:30Z","timestamp":1186218150000},"page":"141-155","source":"Crossref","is-referenced-by-count":2,"title":["On Proof Complexity of Circumscription"],"prefix":"10.1007","author":[{"given":"Uwe","family":"Egly","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans","family":"Tompits","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,7,21]]},"reference":[{"issue":"2","key":"19_CR1","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1093\/logcom\/6.2.205","volume":"6","author":"G. Amati","year":"1996","unstructured":"G. Amati, L. C. Aiello, D. Gabbay and F. Pirri. A Proof Theoretical Approach to Default Reasoning I: Tableaux for Default Logic. Journal of Logic and Computation, 6(2):205\u2013231, 1996.","journal-title":"Journal of Logic and Computation"},{"key":"19_CR2","series-title":"Technical Report","volume-title":"A Gentzen System for Non-Theorems","author":"P. A. Bonatti","year":"1993","unstructured":"P. A. Bonatti. A Gentzen System for Non-Theorems. Technical Report CD-TR 93\/52, Christian Doppler Labor f\u00fcr Expertensysteme, Technische Universit\u00e4t Wien, Paniglgasse 16, A-1040 Wien, 1993."},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"P. A. Bonatti. Sequent Calculi for Default and Autoepistemic Logics. Proceedings TABLEAUX\u201996, Springer LNAI 1071, pp. 127\u2013142, 1996.","DOI":"10.1007\/3-540-61208-4_9"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"P. A. Bonatti and N. Olivetti. A Sequent Calculus for Skeptical Default Logic. Proceedings TABLEAUX\u201997, Springer LNAI 1227, pp. 107\u2013121, 1997.","DOI":"10.1007\/BFb0027408"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"P.A. Bonatti and N. Olivetti. A Sequent Calculus for Circumscription. Preliminary Proceedings CSL\u201997, BRICS Notes Series NS-97-1, pp. 95\u2013107, 1997.","DOI":"10.1007\/BFb0028009"},{"key":"19_CR6","unstructured":"M. Cadoli, F. M. Donini, and M. Schaerf. Is Intractability of Non-Monotonic Reasoning a Real Drawback? In Proceedings of the AAAI National Conference on Artificial Intelligence, pages 946\u2013951. MIT Press, 1994."},{"key":"19_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/3-540-59042-0_74","volume-title":"Proceedings STACS\u2019 95","author":"M. Cadoli","year":"1995","unstructured":"M. Cadoli, F. M. Donini, and M. Schaerf. On Compact Representation of Propositional Circumscription. In Proceedings STACS\u2019 95, Springer LNCS 900, pp. 205\u2013216, 1995."},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0743-1066(93)90029-G","volume":"17","author":"M. Cadoli","year":"1993","unstructured":"M. Cadoli and M. Schaerf. A Survey of Complexity Results for Non-Monotonic Logics. Journal of Logic Programming, 17:127\u2013160, 1993.","journal-title":"Journal of Logic Programming"},{"key":"19_CR9","first-page":"293","volume-title":"Logic and Databases","author":"K. L. Clark","year":"1978","unstructured":"K. L. Clark. Negation as Failure. In Logic and Databases, Plenum, New York, pp. 293\u2013322, 1978."},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"U. Egly and H. Tompits. Is Nonmonotonic Reasoning Always Harder? Proceedings LPNMR\u201997, Springer LNAI 1265, pp. 60\u201375, 1997.","DOI":"10.1007\/3-540-63255-7_5"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"U. Egly and H. Tompits. Non-Elementary Speed-Ups in Default Reasoning. Proceedings ECSQARU-FAPR\u201997, Springer LNAI 1244, pp. 237\u2013251, 1997.","DOI":"10.1007\/BFb0035626"},{"issue":"2","key":"19_CR12","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0304-3975(93)90073-3","volume":"114","author":"T. Eiter","year":"1993","unstructured":"T. Eiter and G. Gottlob. Propositional Circumscription and Extended Closed World Reasoning are II 2 P -complete. Journal of Theoretical Computer Science, 114(2):231\u2013245, 1993. Addendum: vol. 118, p. 315, 1993.","journal-title":"Journal of Theoretical Computer Science"},{"issue":"2","key":"19_CR13","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/BF01054714","volume":"53","author":"V. Goranko","year":"1994","unstructured":"V. Goranko. Refutation Systems in Modal Logic. Studia Logica, 53(2):299\u2013324, 1994.","journal-title":"Studia Logica"},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1093\/logcom\/2.3.397","volume":"2","author":"G. Gottlob","year":"1992","unstructured":"G. Gottlob. Complexity Results for Nonmonotonic Logics. Journal of Logic and Computation, 2:397\u2013425, 1992.","journal-title":"Journal of Logic and Computation"},{"key":"19_CR15","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0004-3702(91)90011-8","volume":"49","author":"H. A. Kautz","year":"1990","unstructured":"H. A. Kautz and B. Selman. Hard Problems for Simple Default Logics. Artificial Intelligence, 49:243\u2013379, 1990.","journal-title":"Artificial Intelligence"},{"key":"19_CR16","first-page":"121","volume-title":"Proceedings of IJCAI\u201985","author":"V. Lifschitz","year":"1985","unstructured":"V. Lifschitz. Computing Circumscription. In Proceedings of IJCAI\u201985, Morgan Kaufmann, Los Altos, CA, pp. 121\u2013127, 1985."},{"key":"19_CR17","volume-title":"Aristotle\u2019s Syllogistic from the Standpoint of Modern Formal Logic","author":"J. \u0141ukasiewicz","year":"1951","unstructured":"J. \u0141ukasiewicz. Aristotle\u2019s Syllogistic from the Standpoint of Modern Formal Logic. Clarendon Press, Oxford, 1951."},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF01543477","volume":"5","author":"W. Marek","year":"1992","unstructured":"W. Marek, A. Nerode and J. Remmel. A Theory of Nonmonotonic Rule Systems II. Annals of Mathematics and Artificial Intelligence, 5:229\u2013264, 1992.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"19_CR19","unstructured":"J. McCarthy. Epistemological Problems of Artificial Intelligence. In Proceedings of IJCAI\u201977, Cambridge, MA, pp. 1038\u20131044, 1977."},{"key":"19_CR20","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0004-3702(80)90011-9","volume":"13","author":"J. McCarthy","year":"1980","unstructured":"J. McCarthy. Circumscription \u2014 A Form of Non-Monotonic Reasoning. Artificial Intelligence, 13:27\u201339, 1980.","journal-title":"Artificial Intelligence"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"I. Niemel\u00e4. A Tableau Calculus for Minimal Model Reasoning. Proceedings TABLEAUX\u201996, Springer LNAI 1071, pp. 278\u2013294, 1996.","DOI":"10.1007\/3-540-61208-4_18"},{"key":"19_CR22","first-page":"80","volume-title":"Proceedings ECAI\u201996","author":"I. Niemel\u00e4","year":"1996","unstructured":"I. Niemel\u00e4. Implementing Circumscription Using a Tableau Method. Proceedings ECAI\u201996, John Wiley & Sons Ltd., Chichester, pp. 80\u201384, 1996."},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF00247828","volume":"9","author":"N. Olivetti","year":"1992","unstructured":"N. Olivetti. Tableaux and Sequent Calculus for Minimal Entailment. Journal of Automated Reasoning, 9:99\u2013139, 1992.","journal-title":"Journal of Automated Reasoning"},{"key":"19_CR24","first-page":"137","volume":"88","author":"V. P. Orevkov","year":"1979","unstructured":"V. P. Orevkov. Lower Bounds for Increasing Complexity of Derivations after Cut Elimination. Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im V. A. Steklova AN SSSR, 88:137\u2013161, 1979. English translation in Journal of Soviet Mathematics, 2337\u20132350, 1982.","journal-title":"Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im V. A. Steklova AN SSSR"},{"key":"19_CR25","first-page":"55","volume-title":"Logic and Databases","author":"R. Reiter","year":"1978","unstructured":"R. Reiter. On Closed-World Data Bases. In Logic and Databases, pp. 55\u201376, Plenum, New York, 1978."},{"key":"19_CR26","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0168-0072(87)90062-5","volume":"35","author":"J. Schlipf","year":"1987","unstructured":"J. Schlipf. Decidability and Definability with Circumscription. Annals of Pure and Applied Logic, 35:173\u2013191, 1987.","journal-title":"Annals of Pure and Applied Logic"},{"key":"19_CR27","first-page":"112","volume":"19","author":"A. Varzi","year":"1990","unstructured":"A. Varzi. Complementary Sentential Logics. Bulletin of the Section of Logic, 19:112\u2013116, 1990.","journal-title":"Bulletin of the Section of Logic"}],"container-title":["Lecture Notes in Computer Science","Automated Reasoning with Analytic Tableaux and Related Methods"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-69778-0_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T19:07:21Z","timestamp":1556737641000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-69778-0_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540644064","9783540697787"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-69778-0_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}