{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T07:28:36Z","timestamp":1672558116007},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,3,10]],"date-time":"2011-03-10T00:00:00Z","timestamp":1299715200000},"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-011-9320-0","type":"journal-article","created":{"date-parts":[[2011,3,9]],"date-time":"2011-03-09T18:17:55Z","timestamp":1299694675000},"page":"446-491","source":"Crossref","is-referenced-by-count":3,"title":["Trichotomies in the Complexity of Minimal Inference"],"prefix":"10.1007","volume":"50","author":[{"given":"Arnaud","family":"Durand","sequence":"first","affiliation":[]},{"given":"Miki","family":"Hermann","sequence":"additional","affiliation":[]},{"given":"Gustav","family":"Nordh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,3,10]]},"reference":[{"issue":"2","key":"9320_CR1","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/BF01187059","volume":"143","author":"K.A. Baker","year":"1975","unstructured":"Baker, K.A., Pixley, A.F.: Polynomial interpolation and the Chinese Remainder Theorem for algebraic systems. Math. Z. 143(2), 165\u2013174 (1975)","journal-title":"Math. Z."},{"issue":"4","key":"9320_CR2","first-page":"38","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, Complexity Theory Column 42 34(4), 38\u201352 (2003)","journal-title":"SIGACT News, Complexity Theory Column 42"},{"issue":"1","key":"9320_CR3","first-page":"22","volume":"35","author":"E. B\u00f6hler","year":"2004","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part II: Constraint satisfaction problems. SIGACT News, Complexity Theory Column 43 35(1), 22\u201335 (2004)","journal-title":"SIGACT News, Complexity Theory Column 43"},{"issue":"2","key":"9320_CR4","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.ipl.2005.06.003","volume":"96","author":"E. B\u00f6hler","year":"2005","unstructured":"B\u00f6hler, E., Reith, S., Schnoor, H., Vollmer, H.: Bases for Boolean co-clones. Inf. Process. Lett. 96(2), 59\u201366 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9320_CR5","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0020-0190(92)90049-2","volume":"44","author":"M. Cadoli","year":"1992","unstructured":"Cadoli, M.: The complexity of model checking for circumscriptive formulae. Inf. Process. Lett. 44(3), 113\u2013118 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9320_CR6","doi-asserted-by":"crossref","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. 48(2), 255\u2013310 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9320_CR7","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1006\/inco.1995.1087","volume":"119","author":"Z.-Z. Chen","year":"1995","unstructured":"Chen, Z.-Z., Toda, S.: The complexity of selecting maximal solutions. Inf. Comput. 119(2), 231\u2013239 (1995)","journal-title":"Inf. Comput."},{"key":"9320_CR8","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity Classifications of Boolean Constraint Satisfaction Problems","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, vol.\u00a07. SIAM, Philadelphia (2001)"},{"key":"9320_CR9","unstructured":"Dalmau, V.: Computational complexity of problems over generalized formulas. PhD thesis, Department de Llenguatges i Sistemes Inform\u00e0tica, Universitat Polit\u00e9cnica de Catalunya, 2000"},{"issue":"2\u20133","key":"9320_CR10","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0004-3702(92)90027-U","volume":"56","author":"J. Kleer de","year":"1992","unstructured":"de Kleer, J., Mackworth, A.K., Reiter, R.: Characterizing diagnoses and systems. Artif. Intell. 56(2\u20133), 197\u2013222 (1992)","journal-title":"Artif. Intell."},{"key":"9320_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/3-540-36494-3_40","volume-title":"Proceedings 20th Symposium on Theoretical Aspects of Computer Science (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.) Proceedings 20th Symposium on Theoretical Aspects of Computer Science (STACS 2003). Lecture Notes in Computer Science, vol.\u00a02607, pp. 451\u2013462. Springer, Berlin (2003)"},{"key":"9320_CR12","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1109\/LICS.2009.14","volume-title":"Proceedings 24th Annual IEEE Symposium on Logic in Computer Science (LICS 2009)","author":"A. Durand","year":"2009","unstructured":"Durand, A., Hermann, M., Nordh, G.: Trichotomy in the complexity of minimal inference. In: Proceedings 24th Annual IEEE Symposium on Logic in Computer Science (LICS 2009), Los Angeles (CA, USA), pp. 387\u2013396 (2009)"},{"issue":"2","key":"9320_CR13","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0304-3975(93)90073-3","volume":"114","author":"T. Eiter","year":"1993","unstructured":"Eiter, T., Gottlob, G.: Propositional circumscription and extended closed-world reasoning are $\\mathrm{\\Pi}_{2}^{\\mathrm{p}}$ -complete. Theor. Comput. Sci. 114(2), 231\u2013245 (1993)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9320_CR14","doi-asserted-by":"crossref","first-page":"95","DOI":"10.2140\/pjm.1968.27.95","volume":"27","author":"D. Geiger","year":"1968","unstructured":"Geiger, D.: Closed systems of functions and predicates. Pac. J. Math. 27(1), 95\u2013100 (1968)","journal-title":"Pac. J. Math."},{"key":"9320_CR15","first-page":"1070","volume-title":"Proceeding 5th International Conference and Symposium on Logic Programming ICLP\/SLP","author":"M. Gelfond","year":"1988","unstructured":"Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Kowalski, R.A., Bowen, K.A. (eds.) Proceeding 5th International Conference and Symposium on Logic Programming ICLP\/SLP, Seatle (WA), pp. 1070\u20131080. MIT Press, Cambridge (1988)"},{"issue":"1","key":"9320_CR16","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, H., Przymusinski, T.C.: On the relationship between circumscription and negation as failure. Artif. Intell. 38(1), 75\u201394 (1989)","journal-title":"Artif. Intell."},{"issue":"4","key":"9320_CR17","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. J. Assoc. Comput. Mach. 44(4), 527\u2013548 (1997)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"4","key":"9320_CR18","doi-asserted-by":"crossref","first-page":"966","DOI":"10.1137\/S0895480103428338","volume":"19","author":"L. Khachiyan","year":"2005","unstructured":"Khachiyan, L., Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: On the complexity of some enumeration problems for matroids. SIAM J. Discrete Math. 19(4), 966\u2013984 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"9320_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1007\/3-540-45402-0_3","volume-title":"Proceedings 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNRM 2001)","author":"L.M. Kirousis","year":"2001","unstructured":"Kirousis, L.M., Kolaitis, P.G.: On the complexity of model checking and inference in minimal models. In: Eiter, T., Faber, W., Truszczy\u0144ski, M. (eds.) Proceedings 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNRM 2001), Vienna (Austria). Lecture Notes in Computer Science, vol. 2173, pp. 42\u201353. Springer, Berlin (2001)"},{"issue":"1","key":"9320_CR20","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":"9320_CR21","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 dichotomy in the complexity of propositional circumscription. Theory Comput. Syst. 37(6), 695\u2013715 (2004)","journal-title":"Theory Comput. Syst."},{"issue":"1\u20132","key":"9320_CR22","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0004-3702(80)90011-9","volume":"13","author":"J. McCarthy","year":"1980","unstructured":"McCarthy, J.: Circumscription\u2014a form of non-monotonic reasoning. Artif. Intell. 13(1\u20132), 27\u201339 (1980)","journal-title":"Artif. Intell."},{"issue":"1","key":"9320_CR23","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0004-3702(86)90032-9","volume":"28","author":"J. McCarthy","year":"1986","unstructured":"McCarthy, J.: Applications of circumscription to formalizing common-sense knowledge. Artif. Intell. 28(1), 89\u2013116 (1986)","journal-title":"Artif. Intell."},{"key":"9320_CR24","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":"Proceedings 11th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2004)","author":"G. Nordh","year":"2005","unstructured":"Nordh, G.: A trichotomy in the complexity of propositional circumscription. In: Baader,\u00a0F., Voronkov,\u00a0A. (eds.) Proceedings 11th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2004), Montevideo (Uruguay). Lecture Notes in Computer Science, vol. 3452, pp. 257\u2013269. Springer, Berlin (2005)"},{"key":"9320_CR25","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1109\/LICS.2004.1319631","volume-title":"Proceedings 19th IEEE Symposium on Logic in Computer Science (LICS 2004)","author":"G. Nordh","year":"2004","unstructured":"Nordh, G., Jonsson, P.: An algebraic approach to the complexity of propositional circumscription. In: Proceedings 19th IEEE Symposium on Logic in Computer Science (LICS 2004), Turku (Finland), pp.\u00a0367\u2013376 (2004)"},{"key":"9320_CR26","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1109\/ISMVL.2009.10","volume-title":"Proceedings 39th International Symposium on Multiple-Valued Logic (ISMVL 2009)","author":"G. Nordh","year":"2009","unstructured":"Nordh, G., Zanuttini, B.: Frozen Boolean partial co-clones. In: Proceedings 39th International Symposium on Multiple-Valued Logic (ISMVL 2009), Naha (Okinawa, Japan), pp. 120\u2013125. IEEE Computer Society, Los Alamitos (2009)"},{"key":"9320_CR27","unstructured":"International Workshop on Mathematics of Constraint Satisfaction. Open problems list. http:\/\/www.cs.rhul.ac.uk\/home\/green\/mathscsp\/slides\/problems\/OpenProblemsList.pdf , March 2006"},{"key":"9320_CR28","first-page":"163","volume-title":"Proceedings 32nd IEEE Symposium on Foundations of Computer Science (FOCS\u201991), San Juan (Puerto Rico)","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H.: On selecting a satisfying truth assignment (extended abstract). In: Proceedings 32nd IEEE Symposium on Foundations of Computer Science (FOCS\u201991), San Juan (Puerto Rico), pp.\u00a0163\u2013169. IEEE Computer Society, Los Alamitos (1991)"},{"key":"9320_CR29","volume-title":"Theories of Computability","author":"N. Pippenger","year":"1997","unstructured":"Pippenger, N.: Theories of Computability. Cambridge University Press, Cambridge (1997)"},{"key":"9320_CR30","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/978-1-4020-1898-5_5","volume-title":"Galois Connections and Applications","author":"R. P\u00f6schel","year":"2004","unstructured":"P\u00f6schel, R.: Galois connection for operations and relations. In: Denecke, K., Ern\u00e9, M., Wismath, S.L. (eds.) Galois Connections and Applications, pp. 231\u2013258. Kluwer Academic, Norwell (2004)"},{"key":"9320_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-5547-1","volume-title":"Funktionen- und Relationenalgebren","author":"R. P\u00f6schel","year":"1979","unstructured":"P\u00f6schel, R., Kalu\u017enin, L.A.: Funktionen- und Relationenalgebren. Deutscher Verlag der Wissenschaften, Berlin (1979)"},{"key":"9320_CR32","first-page":"1","volume":"5","author":"E.L. Post","year":"1941","unstructured":"Post, E.L.: The two-valued iterative systems of mathematical logic. Ann. Math. Stud. 5, 1\u2013122 (1941)","journal-title":"Ann. Math. Stud."},{"issue":"1","key":"9320_CR33","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XIII: the disjoint paths problem. J. Comb. Theory, Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9320_CR34","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF01069627","volume":"17","author":"B.A. Romov","year":"1981","unstructured":"Romov, B.A.: The algebras of partial functions and their invariants. Cybern. Syst. Anal. 17(2), 157\u2013167 (1981)","journal-title":"Cybern. Syst. Anal."},{"key":"9320_CR35","first-page":"216","volume-title":"Proceedings 10th Symposium on Theory of Computing (STOC\u201978)","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings 10th Symposium on Theory of Computing (STOC\u201978), San Diego (CA, USA), pp. 216\u2013226 (1978)"},{"key":"9320_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/978-3-540-92800-3_9","volume-title":"Complexity of Constraints","author":"H. Schnoor","year":"2008","unstructured":"Schnoor, H., Schnoor, I.: Partial polymorphisms and constraint satisfaction problems. In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Complexity of Constraints. Lecture Notes in Computer Science, vol. 5250, pp. 229\u2013254. Springer, Berlin (2008)"},{"key":"9320_CR37","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":"Proceedings 10th International Conference om Logic Programming and Nonmonotonic Reasoning (LPNMR 2009)","author":"M. Thomas","year":"2009","unstructured":"Thomas, M.: The complexity of circumscriptive inference in Post\u2019s lattice. In: Erdem, E., Lin, F., Schaub, T. (eds.) Proceedings 10th International Conference om Logic Programming and Nonmonotonic Reasoning (LPNMR 2009), Potsdam (Germany). Lecture Notes in Computer Science, vol. 5753, pp. 290\u2013302. Springer, Berlin (2009)"},{"key":"9320_CR38","first-page":"53","volume":"102","author":"M. Thomas","year":"2010","unstructured":"Thomas, M., Vollmer, H.: Complexity of non-monotonic logics. Bull. Eur. Assoc. Theor. Comput. Sci. 102, 53\u201382 (2010)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9320-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9320-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9320-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:22Z","timestamp":1558698862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9320-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,10]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9320"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9320-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,10]]}}}