{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T16:53:32Z","timestamp":1773939212864,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642042379","type":"print"},{"value":"9783642042386","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04238-6_25","type":"book-chapter","created":{"date-parts":[[2009,8,31]],"date-time":"2009-08-31T08:23:01Z","timestamp":1251706981000},"page":"290-302","source":"Crossref","is-referenced-by-count":8,"title":["The Complexity of Circumscriptive Inference in Post\u2019s Lattice"],"prefix":"10.1007","author":[{"given":"Michael","family":"Thomas","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-540-71389-0_5","volume-title":"Foundations of Software Science and Computational Structures","author":"M. Bauland","year":"2007","unstructured":"Bauland, M., Schneider, T., Schnoor, H., Schnoor, I., Vollmer, H.: The complexity of generalized satisfiability for linear temporal logic. In: Seidl, H. (ed.) FOSSACS 2007. LNCS, vol.\u00a04423, pp. 48\u201362. Springer, Heidelberg (2007)"},{"key":"25_CR2","unstructured":"Beyersdorff, O., Meier, A., Thomas, M., Vollmer, H.: The complexity of propositional implication. ACM CoRR, arXiv:0811.0959v1 [cs.CC] (2008)"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-3-642-02777-2_7","volume-title":"SAT 2009","author":"O. Beyersdorff","year":"2009","unstructured":"Beyersdorff, O., Meier, A., Thomas, M., Vollmer, H.: The complexity of reasoning for fragments of default logic. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol.\u00a05584, pp. 51\u201364. Springer, Heidelberg (2009)"},{"issue":"4","key":"25_CR4","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/954092.954101","volume":"34","author":"E. B\u00f6hler","year":"2003","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part I: Post\u2019s lattice with applications to complexity theory. SIGACT News\u00a034(4), 38\u201352 (2003)","journal-title":"SIGACT News"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF01374526","volume":"25","author":"G. Buntrock","year":"1992","unstructured":"Buntrock, G., Damm, C., Hertrampf, U., Meinel, C.: Structure and importance of logspace MOD-classes. Mathematical Systems Theory\u00a025, 223\u2013237 (1992)","journal-title":"Mathematical Systems Theory"},{"key":"25_CR6","first-page":"205","volume":"182","author":"M. Cadoli","year":"1995","unstructured":"Cadoli, M., Donini, F., Schaerf, M.: On compact representations of propositional circumscription. Theor. Comput. Sci.\u00a0182, 205\u2013216 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"25_CR7","unstructured":"Cadoli, M., Lenzerini, M.: The complexity of closed world reasoning and circumscription. In: Proc. 8th AAAI, pp. 550\u2013555 (1990)"},{"issue":"2","key":"25_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0022-0000(05)80004-2","volume":"48","author":"M. Cadoli","year":"1994","unstructured":"Cadoli, M., Lenzerini, M.: The complexity of propositional closed world reasoning and circumscription. J. Comput. Syst. Sci.\u00a048(2), 255\u2013310 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/3-540-36494-3_40","volume-title":"STACS 2003","author":"A. Durand","year":"2003","unstructured":"Durand, A., Hermann, M.: The inference problem for propositional circumscription of affine formulas is coNP-complete. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 451\u2013462. Springer, Heidelberg (2003)"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Durand, A., Hermann, M., Nordh, G.: Trichotomies in the complexity of minimal inference (2008), http:\/\/www.ida.liu.se\/~gusno\/","DOI":"10.1109\/LICS.2009.14"},{"key":"#cr-split#-25_CR11.1","doi-asserted-by":"crossref","unstructured":"Eiter, T., Gottlob, G.: Propositional circumscription and extended closed world reasoning are $\\Pi_2^p$ -complete. Theor. Comput. Sci.??114(2), 231???245 (1993);","DOI":"10.1016\/0304-3975(93)90073-3"},{"key":"#cr-split#-25_CR11.2","doi-asserted-by":"crossref","unstructured":"Addendum in TCS 118, p. 15 (1993)","DOI":"10.1002\/ppul.1950150616"},{"issue":"1","key":"25_CR12","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0004-3702(89)90068-4","volume":"38","author":"M. Gelfond","year":"1989","unstructured":"Gelfond, M., Przymusinska, H., Przymusinski, T.C.: On the relationship between circumscription and negation as failure. Artificial Intelligence\u00a038(1), 75\u201394 (1989)","journal-title":"Artificial Intelligence"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Kirousis, L.M., Kolaitis, P.: The complexity of minimal satisfiability in Post\u2019s lattice. Unpublished notes (2001)","DOI":"10.1007\/3-540-44693-1_36"},{"issue":"1","key":"25_CR14","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/S0890-5401(03)00037-3","volume":"187","author":"L.M. Kirousis","year":"2003","unstructured":"Kirousis, L.M., Kolaitis, P.G.: The complexity of minimal satisfiability problems. Inf. Comput.\u00a0187(1), 20\u201339 (2003)","journal-title":"Inf. Comput."},{"issue":"6","key":"25_CR15","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1007\/s00224-004-1152-8","volume":"37","author":"L.M. Kirousis","year":"2004","unstructured":"Kirousis, L.M., Kolaitis, P.G.: A dichotomy in the complexity of propositional circumscription. Theory Comput. Syst.\u00a037(6), 695\u2013715 (2004)","journal-title":"Theory Comput. Syst."},{"key":"25_CR16","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01744287","volume":"13","author":"H. Lewis","year":"1979","unstructured":"Lewis, H.: Satisfiability problems for propositional calculi. Mathematical Systems Theory\u00a013, 45\u201353 (1979)","journal-title":"Mathematical Systems Theory"},{"key":"25_CR17","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0004-3702(80)90011-9","volume":"13","author":"J. McCarthy","year":"1980","unstructured":"McCarthy, J.: Circumscription \u2013 A form of non-monotonic reasoning. Artificial Intelligence\u00a013, 27\u201339 (1980)","journal-title":"Artificial Intelligence"},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"Meier, A., Mundhenk, M., Thomas, M., Vollmer, H.: The complexity of satisfiability for fragments of CTL and CTL\u2009\u22c6\u2009. In: Proc. 2nd Workshop on Reachability Problems, pp. 201\u2013213 (2008)","DOI":"10.1016\/j.entcs.2008.12.040"},{"key":"25_CR19","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-540-32275-7_18","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"G. Nordh","year":"2005","unstructured":"Nordh, G.: A trichotomy in the complexity of propositional circumscription. In: Baader, F., Voronkov, A. (eds.) LPAR 2004. LNCS (LNAI), vol.\u00a03452, pp. 257\u2013269. Springer, Heidelberg (2005)"},{"key":"25_CR20","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"25_CR21","volume-title":"Theories of Computability","author":"N. Pippenger","year":"1997","unstructured":"Pippenger, N.: Theories of Computability. Cambridge University Press, Cambridge (1997)"},{"key":"25_CR22","first-page":"1","volume":"5","author":"E. Post","year":"1941","unstructured":"Post, E.: The two-valued iterative systems of mathematical logic. Annals of Mathematical Studies\u00a05, 1\u2013122 (1941)","journal-title":"Annals of Mathematical Studies"},{"key":"25_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1007\/978-3-540-45138-9_57","volume-title":"Mathematical Foundations of Computer Science 2003","author":"S. Reith","year":"2003","unstructured":"Reith, S.: On the complexity of some equivalence problems for propositional calculi. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol.\u00a02747, pp. 632\u2013641. Springer, Heidelberg (2003)"},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"Reith, S., Wagner, K.: The complexity of problems defined by Boolean circuits. In: Proc. MFI 1999, pp. 141\u2013156. World Science Publishing (2005)","DOI":"10.1142\/9789812703118_0014"},{"key":"25_CR25","first-page":"216","volume-title":"Proc. 10th STOC","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. 10th STOC, pp. 216\u2013226. ACM Press, New York (1978)"},{"key":"25_CR26","unstructured":"Schnoor, H.: The complexity of the Boolean formula value problem. Technical report, Theoretical Computer Science, University of Hannover (2005)"},{"key":"25_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity. Springer, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","Logic Programming and Nonmonotonic Reasoning"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04238-6_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T22:08:59Z","timestamp":1590098939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04238-6_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642042379","9783642042386"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04238-6_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}