{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:30:11Z","timestamp":1757543411540,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540372066"},{"type":"electronic","value":"9783540372073"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11814948_4","type":"book-chapter","created":{"date-parts":[[2006,7,18]],"date-time":"2006-07-18T10:12:38Z","timestamp":1153217558000},"page":"22-35","source":"Crossref","is-referenced-by-count":25,"title":["Categorisation of Clauses in Conjunctive Normal Forms: Minimally Unsatisfiable Sub-clause-sets and the Lean Kernel"],"prefix":"10.1007","author":[{"given":"Oliver","family":"Kullmann","sequence":"first","affiliation":[]},{"given":"In\u00eas","family":"Lynce","sequence":"additional","affiliation":[]},{"given":"Jo\u00e3o","family":"Marques-Silva","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/0097-3165(86)90060-9","volume":"43","author":"R. Aharoni","year":"1986","unstructured":"Aharoni, R., Linial, N.: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. Journal of Combinatorial Theory, A\u00a043, 196\u2013204 (1986)","journal-title":"Journal of Combinatorial Theory, A"},{"key":"4_CR2","series-title":"North-Holland Mathematical Library","doi-asserted-by":"publisher","DOI":"10.1016\/S0924-6509(08)70096-5","volume-title":"Hypergraphs: Combinatorics of Finite Sets","author":"C. Berge","year":"1989","unstructured":"Berge, C.: Hypergraphs: Combinatorics of Finite Sets. North-Holland Mathematical Library, vol.\u00a045. North-Holland, Amsterdam (1989)"},{"key":"4_CR3","volume-title":"Advances in Computers, Chapter Bounded model checking","author":"A. Biere","year":"2003","unstructured":"Biere, A., Cimatti, A., Clarke, E.M., Strichman, O., Zhu, Y.: Highly Dependable Software. In: Advances in Computers, Chapter Bounded model checking, vol.\u00a058, Elsevier, Amsterdam (2003)"},{"key":"4_CR4","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s10472-005-0418-4","volume":"43","author":"R. Bruni","year":"2005","unstructured":"Bruni, R.: On exact selection of minimally unsatisfiable subformulae. Annals for Mathematics and Artificial Intelligence\u00a043, 35\u201350 (2005)","journal-title":"Annals for Mathematics and Artificial Intelligence"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Bruni, R., Sassano, A.: Restoring satisfiability or maintaining unsatisfiability by finding small unsatisfiable subformulae. In: LICS Workshop SAT 2001. ENDM, vol.\u00a09 (2001)","DOI":"10.1016\/S1571-0653(04)00320-8"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0166-218X(00)00245-6","volume":"107","author":"H.K. B\u00fcning","year":"2000","unstructured":"B\u00fcning, H.K.: On subclasses of minimal unsatisfiable formulas. Discrete Applied Mathematics\u00a0107, 83\u201398 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Chauhan, P., Clarke, E., Kukula, J., Sapra, S., Veith, H., Wang, D.: Automated abstraction refinement for model checking large state spaces using SAT based conflict analysis. In: International Conference on Formal Methods in Computer-Aided Design (2002)","DOI":"10.1007\/3-540-36126-X_3"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: A short proof of the pigeonhole principle using extended resolution. In: SIGACT News, October-December 1976, pp. 28\u201332 (1976)","DOI":"10.1145\/1008335.1008338"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1023\/A:1018924526592","volume":"23","author":"G. Davydov","year":"1998","unstructured":"Davydov, G., Davydova, I., B\u00fcning, H.K.: An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF. Annals of Mathematics and Artificial Intelligence\u00a023, 229\u2013245 (1998)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"de la Banda, M.G., Stuckey, P.J., Wazny, J.: Finding all minimal unsatisfiable sub-sets. In: International Conference on Principles and Practice of Declarative Programming (2003)","DOI":"10.1145\/888251.888256"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Goldberg, E., Novikov, Y.: Verification of proofs of unsatisfiability for CNF formulas. In: Design, Automation and Test in Europe Conference, March 2003, pp. 10886\u201310891 (2003)","DOI":"10.1109\/DATE.2003.1253718"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Kullmann, O.: An application of matroid theory to the SAT problem. In: Fifteenth Annual IEEE Conference on Computational Complexity, pp. 116\u2013124 (2003)","DOI":"10.1109\/CCC.2000.856741"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Kullmann, O.: On the use of autarkies for satisfiability decision. In: LICS Workshop SAT 2001. ENDM, vol.\u00a09 (2001)","DOI":"10.1016\/S1571-0653(04)00325-7"},{"issue":"1-2","key":"4_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","volume":"223","author":"O. Kullmann","year":"1999","unstructured":"Kullmann, O.: New methods for 3-SAT decision and worst-case analysis. Theoretical Computer Science\u00a0223(1-2), 1\u201372 (1999)","journal-title":"Theoretical Computer Science"},{"issue":"1-3","key":"4_CR15","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0166-218X(99)00037-2","volume":"96-97","author":"O. Kullmann","year":"1999","unstructured":"Kullmann, O.: On a generalization of extended resolution. Discrete Applied Mathematics\u00a096-97(1-3), 149\u2013176 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0166-218X(00)00262-6","volume":"107","author":"O. Kullmann","year":"2000","unstructured":"Kullmann, O.: Investigations on autark assignments. Discrete Applied Mathematics\u00a0107, 99\u2013137 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0166-218X(02)00406-7","volume":"130","author":"O. Kullmann","year":"2003","unstructured":"Kullmann, O.: Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets. Discrete Applied Mathematics\u00a0130, 209\u2013249 (2003)","journal-title":"Discrete Applied Mathematics"},{"issue":"3-4","key":"4_CR18","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1023\/B:AMAI.0000012871.08577.0b","volume":"40","author":"O. Kullmann","year":"2004","unstructured":"Kullmann, O.: Upper and lower bounds on the complexity of generalised resolution and generalised constraint satisfaction problems. Annals of Mathematics and Artificial Intelligence\u00a040(3-4), 303\u2013352 (2004)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"4_CR19","unstructured":"Kullmann, O.: Modelling the behaviour of a DLL SAT solver on random formulas (preparation, 2006)"},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/11499107_13","volume-title":"Theory and Applications of Satisfiability Testing","author":"M.H. Liffiton","year":"2005","unstructured":"Liffiton, M.H., Sakallah, K.A.: On finding all minimally unsatisfiable subformulas. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol.\u00a03569, pp. 173\u2013186. Springer, Heidelberg (2005)"},{"issue":"3-4","key":"4_CR21","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1023\/A:1018999721141","volume":"22","author":"B. Mazure","year":"1998","unstructured":"Mazure, B., Sais, L., Gr\u00e9goire, E.: Boosting complete techniques thanks to local search methods. Annals of Mathematics and Artificial Intelligence\u00a022(3-4), 319\u2013331 (1998)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"4_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45069-6_1","volume-title":"Computer Aided Verification","author":"K.L. McMillan","year":"2003","unstructured":"McMillan, K.L.: Interpolation and SAT-based model checking. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol.\u00a02725, Springer, Heidelberg (2003)"},{"key":"4_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/11499107_40","volume-title":"Theory and Applications of Satisfiability Testing","author":"M.N. Mneimneh","year":"2005","unstructured":"Mneimneh, M.N., Lynce, I., Andraus, Z.S., Sakallah, K.A., Marques-Silva, J.P.: A branch and bound algorithm for extracting smallest minimal unsatisfiable formulas. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol.\u00a03569, pp. 467\u2013474. Springer, Heidelberg (2005)"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Nam, G.-J., Sakallah, K.A., Rutenbar, R.A.: Satisfiability-based layout revisited: Detailed routing of complex FPGAs via search-based boolean SAT. In: International Symposium on Field-Programmable Gate Arrays (February 1999)","DOI":"10.1145\/296399.296450"},{"key":"4_CR25","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C.H. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The complexity of facets (and some facets of complexity). Journal on Computer and System Sciences\u00a028, 244\u2013259 (1984)","journal-title":"Journal on Computer and System Sciences"},{"issue":"3","key":"4_CR26","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF02916605","volume":"40","author":"M. Shaohan","year":"1997","unstructured":"Shaohan, M., Dongmin, L.: A polynomial-time algorithm for reducing the number of variables in MAX SAT problem. Science in China (Series E)\u00a040(3), 301\u2013311 (1997)","journal-title":"Science in China (Series E)"},{"issue":"1","key":"4_CR27","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1017\/S0890060403171065","volume":"17","author":"C. Sinz","year":"2003","unstructured":"Sinz, C., Kaiser, A., K\u00fcchlin, W.: Formal methods for the validation of automotive product configuration data. Artificial Intelligence for Engineering Design, Analysis and Manufacturing\u00a017(1), 75\u201397 (2003)","journal-title":"Artificial Intelligence for Engineering Design, Analysis and Manufacturing"},{"key":"4_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-540-24605-3_22","volume-title":"Theory and Applications of Satisfiability Testing","author":"L. Zhang","year":"2004","unstructured":"Zhang, L., Malik, S.: Extracting small unsatisfiable cores from unsatisfiable Boolean formula. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 239\u2013249. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing - SAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11814948_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T23:23:00Z","timestamp":1736464980000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11814948_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540372066","9783540372073"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/11814948_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}