{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T01:35:08Z","timestamp":1648949708334},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,1,11]],"date-time":"2011-01-11T00:00:00Z","timestamp":1294704000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,4]]},"DOI":"10.1007\/s00224-010-9311-6","type":"journal-article","created":{"date-parts":[[2011,1,10]],"date-time":"2011-01-10T08:18:44Z","timestamp":1294647524000},"page":"401-419","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Circumscriptive Inference in Post\u2019s Lattice"],"prefix":"10.1007","volume":"50","author":[{"given":"Michael","family":"Thomas","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,1,11]]},"reference":[{"key":"9311_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1007\/11672142_41","volume-title":"Proc. 23rd Symposium on Theoretical Aspects of Computer Science","author":"M. Bauland","year":"2006","unstructured":"Bauland,\u00a0M., Hemaspaandra,\u00a0E., Schnoor,\u00a0H., Schnoor,\u00a0I.: Generalized modal satisfiability. In: Proc. 23rd Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol.\u00a03884, pp.\u00a0500\u2013511. Springer, Berlin (2006)"},{"key":"9311_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/978-3-540-71389-0_5","volume-title":"Proc. 10th FoSSaCS","author":"M. Bauland","year":"2007","unstructured":"Bauland,\u00a0M., Schneider,\u00a0T., Schnoor,\u00a0H., Schnoor,\u00a0I., Vollmer,\u00a0H.: The complexity of generalized satisfiability for Linear Temporal Logic. In: Proc. 10th FoSSaCS. Lecture Notes in Computer Science, vol.\u00a04423, pp.\u00a048\u201362. Springer, Berlin (2007)"},{"issue":"18","key":"9311_CR3","doi-asserted-by":"crossref","first-page":"1071","DOI":"10.1016\/j.ipl.2009.06.015","volume":"109","author":"O. Beyersdorff","year":"2009","unstructured":"Beyersdorff,\u00a0O., Meier,\u00a0A., Thomas,\u00a0M., Vollmer,\u00a0H.: The complexity of propositional implication. Inf. Process. Lett. 109(18), 1071\u20131077 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9311_CR4","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":"Proc. 12th International Conference on Theory and Applications of Satisfiability Testing","author":"O. Beyersdorff","year":"2009","unstructured":"Beyersdorff,\u00a0O., Meier,\u00a0A., Thomas,\u00a0M., Vollmer,\u00a0H.: The complexity of reasoning for fragments of default logic. In: Proc. 12th International Conference on Theory and Applications of Satisfiability Testing. Lecture Notes in Computer Science, vol.\u00a05584, pp.\u00a051\u201364. Springer, Berlin (2009)"},{"issue":"4","key":"9311_CR5","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/954092.954101","volume":"34","author":"E. B\u00f6hler","year":"2003","unstructured":"B\u00f6hler,\u00a0E., Creignou,\u00a0N., Reith,\u00a0S., Vollmer,\u00a0H.: Playing with Boolean blocks, part I: Post\u2019s lattice with applications to complexity theory. SIGACT News 34(4), 38\u201352 (2003)","journal-title":"SIGACT News"},{"key":"9311_CR6","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF01374526","volume":"25","author":"G. Buntrock","year":"1992","unstructured":"Buntrock,\u00a0G., Damm,\u00a0C., Hertrampf,\u00a0U., Meinel,\u00a0C.: Structure and importance of logspace MOD-classes. Math. Syst. Theory 25, 223\u2013237 (1992)","journal-title":"Math. Syst. Theory"},{"key":"9311_CR7","first-page":"205","volume":"182","author":"M. Cadoli","year":"1995","unstructured":"Cadoli,\u00a0M., Donini,\u00a0F., Schaerf,\u00a0M.: On compact representations of propositional circumscription. Theor. Comput. Sci. 182, 205\u2013216 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"9311_CR8","first-page":"550","volume-title":"Proc. 8th National Conference on Artificial Intelligence","author":"M. Cadoli","year":"1990","unstructured":"Cadoli,\u00a0M., Lenzerini,\u00a0M.: The complexity of closed world reasoning and circumscription. In: Proc. 8th National Conference on Artificial Intelligence, pp.\u00a0550\u2013555 (1990)"},{"issue":"2","key":"9311_CR9","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0022-0000(05)80004-2","volume":"48","author":"M. Cadoli","year":"1994","unstructured":"Cadoli,\u00a0M., Lenzerini,\u00a0M.: The complexity of propositional closed world reasoning and circumscription. J. Comput. Syst. Sci. 48(2), 255\u2013310 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"9311_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/3-540-36494-3_40","volume-title":"Proc. 20th Symposium on Theoretical Aspects of Computer Science","author":"A. Durand","year":"2003","unstructured":"Durand,\u00a0A., Hermann,\u00a0M.: The inference problem for propositional circumscription of affine formulas is coNP-complete. In: Proc. 20th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol.\u00a02607, pp.\u00a0451\u2013462. Springer, Berlin (2003)"},{"key":"9311_CR11","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1109\/LICS.2009.14","volume-title":"Proc. 24th Symposium on Logic in Computer Science","author":"A. Durand","year":"2009","unstructured":"Durand,\u00a0A., Hermann,\u00a0M., Nordh,\u00a0G.: Trichotomy in the complexity of minimal inference. In: Proc. 24th Symposium on Logic in Computer Science, pp.\u00a0387\u2013396. IEEE Computer Society, Los Alamitos (2009)"},{"issue":"2","key":"9311_CR12","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0304-3975(93)90073-3","volume":"114","author":"T. Eiter","year":"1993","unstructured":"Eiter,\u00a0T., Gottlob,\u00a0G.: Propositional circumscription and extended closed world reasoning are $\\Pi_{2}^{p}$ -complete. Theor. Comput. Sci. 114(2), 231\u2013245 (1993). Addendum in TCS 118, 15 (1993)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9311_CR13","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0004-3702(89)90068-4","volume":"38","author":"M. Gelfond","year":"1989","unstructured":"Gelfond, M., Przymusinska,\u00a0H., Przymusinski, T.C.: On the relationship between circumscription and negation as failure. Artif. Intell. 38(1), 75\u201394 (1989)","journal-title":"Artif. Intell."},{"key":"9311_CR14","doi-asserted-by":"crossref","unstructured":"Kirousis, L.M., Kolaitis,\u00a0P.: The complexity of minimal satisfiability in Post\u2019s lattice. Unpublished notes (2001)","DOI":"10.1007\/3-540-44693-1_36"},{"issue":"1","key":"9311_CR15","doi-asserted-by":"crossref","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. 187(1), 20\u201339 (2003)","journal-title":"Inf. Comput."},{"issue":"6","key":"9311_CR16","doi-asserted-by":"crossref","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\u00a0dichotomy in the complexity of propositional circumscription. Theory Comput. Syst. 37(6), 695\u2013715 (2004)","journal-title":"Theory Comput. Syst."},{"key":"9311_CR17","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF01744287","volume":"13","author":"H. Lewis","year":"1979","unstructured":"Lewis,\u00a0H.: Satisfiability problems for propositional calculi. Math. Syst. Theory 13, 45\u201353 (1979)","journal-title":"Math. Syst. Theory"},{"key":"9311_CR18","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0004-3702(80)90011-9","volume":"13","author":"J. McCarthy","year":"1980","unstructured":"McCarthy,\u00a0J.: Circumscription\u2014A\u00a0form of non-monotonic reasoning. Artif. Intell. 13, 27\u201339 (1980)","journal-title":"Artif. Intell."},{"issue":"5","key":"9311_CR19","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1142\/S0129054109006954","volume":"20","author":"A. Meier","year":"2009","unstructured":"Meier,\u00a0A., Mundhenk,\u00a0M., Thomas,\u00a0M., Vollmer,\u00a0H.: The complexity of satisfiability for fragments of CTL and CTL\u22c6. Int. J. Found. Comput. Sci. 20(5), 901\u2013918 (2009)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9311_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/978-3-540-32275-7_18","volume-title":"Proc. 11th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning","author":"G. Nordh","year":"2005","unstructured":"Nordh,\u00a0G.: A\u00a0trichotomy in the complexity of propositional circumscription. In: Proc. 11th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning. Lecture Notes in Computer Science, vol.\u00a03452, pp.\u00a0257\u2013269. Springer, Berlin (2005)"},{"key":"9311_CR21","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"9311_CR22","volume-title":"Theories of Computability","author":"N. Pippenger","year":"1997","unstructured":"Pippenger,\u00a0N.: Theories of Computability. Cambridge University Press, Cambridge (1997)"},{"key":"9311_CR23","first-page":"1","volume":"5","author":"E. Post","year":"1941","unstructured":"Post,\u00a0E.: The two-valued iterative systems of mathematical logic. Ann. Math. Stud. 5, 1\u2013122 (1941)","journal-title":"Ann. Math. Stud."},{"key":"9311_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1007\/978-3-540-45138-9_57","volume-title":"Proc. 28th International Symposium on Mathematical Foundations of Computer Science","author":"S. Reith","year":"2003","unstructured":"Reith,\u00a0S.: On the complexity of some equivalence problems for propositional calculi. In: Proc. 28th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, pp.\u00a0632\u2013641. Springer, Berlin (2003)"},{"key":"9311_CR25","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1142\/9789812703118_0014","volume-title":"Proc. International Conference Mathematical Foundation of Informatics 1999","author":"S. Reith","year":"2005","unstructured":"Reith,\u00a0S., Wagner,\u00a0K.: The complexity of problems defined by Boolean circuits. In: Proc. International Conference Mathematical Foundation of Informatics 1999, pp.\u00a0141\u2013156. World Scientific, Singapore (2005)"},{"key":"9311_CR26","first-page":"216","volume-title":"Proc. 10th Symposium on Theory of Computing","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. 10th Symposium on Theory of Computing, pp.\u00a0216\u2013226. ACM, New York (1978)"},{"issue":"3","key":"9311_CR27","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1142\/S0129054110007258","volume":"21","author":"H. Schnoor","year":"2010","unstructured":"Schnoor,\u00a0H.: The complexity of model checking for boolean formulas. Int. J. Found. Comput. Sci. 21(3), 289\u2013309 (2010)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9311_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/978-3-642-04238-6_25","volume-title":"Proc. 10th International Conference on Logic Programming and Nonmonotonic Reasoning","author":"M. Thomas","year":"2009","unstructured":"Thomas,\u00a0M.: The complexity of circumscriptive inference in Post\u2019s lattice. In: Proc. 10th International Conference on Logic Programming and Nonmonotonic Reasoning. Lecture Notes in Computer Science, vol.\u00a05753, pp.\u00a0290\u2013302. Springer, Berlin (2009)"},{"key":"9311_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity","author":"H. Vollmer","year":"1999","unstructured":"Vollmer,\u00a0H.: Introduction to Circuit Complexity. Springer, Berlin (1999)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9311-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-010-9311-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9311-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T18:44:41Z","timestamp":1559933081000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-010-9311-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,11]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9311"],"URL":"https:\/\/doi.org\/10.1007\/s00224-010-9311-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,11]]}}}