{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:31:57Z","timestamp":1750221117203,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,2,18]],"date-time":"2019-02-18T00:00:00Z","timestamp":1550448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NCN","award":["2014\/14\/A\/ST6\/00138"],"award-info":[{"award-number":["2014\/14\/A\/ST6\/00138"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>\n            We study the complexity of the inference problem for propositional circumscription (the minimal inference problem) over arbitrary finite domains. The problem is of fundamental importance in nonmonotonic logics and commonsense reasoning. The complexity of the problem for the two-element domain has been completely classified. In this article, we classify the complexity of the problem over all conservative languages. We consider a version of the problem parameterized by a set of relations (a constraint language), from which we are allowed to build a knowledge base, and where a linear order used to compare models is a part of an input. We show that in this setting the problem is either \u03a0\n            <jats:sup>\n              <jats:italic>P<\/jats:italic>\n            <\/jats:sup>\n            <jats:sub>2<\/jats:sub>\n            -complete, coNP-complete, or in P. The classification is based on a coNP-hardness proof for a new class of languages, an analysis of languages that do not express any member of the class, and a new general polynomial-time algorithm solving the minimal inference problem for a large class of languages.\n          <\/jats:p>","DOI":"10.1145\/3301410","type":"journal-article","created":{"date-parts":[[2019,2,19]],"date-time":"2019-02-19T20:54:15Z","timestamp":1550609655000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Minimal Inference Problem for Conservative Constraint Languages"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2723-0768","authenticated-orcid":false,"given":"Micha\u0142","family":"Wrona","sequence":"first","affiliation":[{"name":"Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, Krak\u00f3w, Poland"}]}],"member":"320","published-online":{"date-parts":[[2019,2,18]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1007\/BF01187059"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1109\/LICS.2011.25"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/2556646"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1137\/070708093"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/1667053.1667058"},{"key":"e_1_2_1_6_1","first-page":"3","article-title":"Galois theory for post algebras, part I and II","volume":"5","author":"Bodnar\u010duk V. G.","year":"1969","unstructured":"V. G. Bodnar\u010duk , L. A. Kalu\u017enin , V. N. Kotov , and B. A. Romov . 1969 . Galois theory for post algebras, part I and II . Cybern. 5 , 3 -- 5 (1969), 243--539. V. G. Bodnar\u010duk, L. A. Kalu\u017enin, V. N. Kotov, and B. A. Romov. 1969. Galois theory for post algebras, part I and II. Cybern. 5, 3--5 (1969), 243--539.","journal-title":"Cybern."},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/1120582.1120584"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/1970398.1970400"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1109\/FOCS.2017.37"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_11_1","volume-title":"Bulatov and D\u00e1niel Marx","author":"Andrei","year":"2010","unstructured":"Andrei A. Bulatov and D\u00e1niel Marx . 2010 . The complexity of global cardinality constraints. Logical Methods in Computer Science 6, 4 (2010). Andrei A. Bulatov and D\u00e1niel Marx. 2010. The complexity of global cardinality constraints. Logical Methods in Computer Science 6, 4 (2010)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1016\/S0022-0000(05)80004-2"},{"volume-title":"Rough-Neural Computing: Techniques for Computing with Words","author":"Doherty Patrick","unstructured":"Patrick Doherty , Jaroslaw Kachniarz , and Andrzej Sza\u0142as . 2004. Using contextually closed queries for local closed-world reasoning in rough knowledge databases . In Rough-Neural Computing: Techniques for Computing with Words . Springer , 219--250. Patrick Doherty, Jaroslaw Kachniarz, and Andrzej Sza\u0142as. 2004. Using contextually closed queries for local closed-world reasoning in rough knowledge databases. In Rough-Neural Computing: Techniques for Computing with Words. Springer, 219--250.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). Springer, 451--462","author":"Durand Arnaud","year":"2003","unstructured":"Arnaud Durand and Miki Hermann . 2003 . The inference problem for propositional circumscription of affine formulas is coNP-complete . In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). Springer, 451--462 . Arnaud Durand and Miki Hermann. 2003. The inference problem for propositional circumscription of affine formulas is coNP-complete. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). Springer, 451--462."},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1007\/s00224-011-9320-0"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1016\/0304-3975(93)90073-3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1137\/S0097539794266766"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.2140\/pjm.1968.27.95"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1016\/0004-3702(89)90068-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1137\/090775646"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/263867.263489"},{"unstructured":"Peter Jonsson. 2014. The Complexity of MINCSP and CSP. (2014). Personal Communication.  Peter Jonsson. 2014. The Complexity of MINCSP and CSP. (2014). Personal Communication.","key":"e_1_2_1_22_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1007\/s00224-004-1152-8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.5555\/2095116.2095177"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1016\/0004-3702(80)90011-9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1016\/0004-3702(86)90032-9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.5555\/1018438.1021873"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1016\/0004-3702(91)90013-A"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). LIPIcs, 657--668","author":"Takhanov Rustem","year":"2010","unstructured":"Rustem Takhanov . 2010 . A dichotomy theorem for the general minimum cost homomorphism problem . In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). LIPIcs, 657--668 . Rustem Takhanov. 2010. A dichotomy theorem for the general minimum cost homomorphism problem. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). LIPIcs, 657--668."},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1007\/978-3-642-39206-1_68"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1007\/978-3-319-61660-5_11"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301410","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3301410","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:05Z","timestamp":1750208525000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301410"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,18]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3301410"],"URL":"https:\/\/doi.org\/10.1145\/3301410","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2019,2,18]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}