{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:40Z","timestamp":1740109420891,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2018,12,20]],"date-time":"2018-12-20T00:00:00Z","timestamp":1545264000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s00224-018-9896-8","type":"journal-article","created":{"date-parts":[[2018,12,20]],"date-time":"2018-12-20T01:34:27Z","timestamp":1545269667000},"page":"1131-1184","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Minimal Distance of Propositional Models"],"prefix":"10.1007","volume":"63","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0050-8085","authenticated-orcid":false,"given":"Mike","family":"Behrisch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2517-2127","authenticated-orcid":false,"given":"Miki","family":"Hermann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1386-8784","authenticated-orcid":false,"given":"Stefan","family":"Mengel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8950-1551","authenticated-orcid":false,"given":"Gernot","family":"Salzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,12,20]]},"reference":[{"issue":"2","key":"9896_CR1","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S Arora","year":"1997","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54 (2), 317\u2013331 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9896_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.R., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inf. Process. Lett. 8(3), 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"key":"9896_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin (1999)"},{"issue":"4","key":"9896_CR4","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10817-006-9063-9","volume":"37","author":"O Bailleux","year":"2006","unstructured":"Bailleux, O., Marquis, P.: Some computational aspects of Distance-SAT. J. Autom. Reason. 37(4), 231\u2013260 (2006)","journal-title":"J. Autom. Reason."},{"issue":"2","key":"9896_CR5","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF01187059","volume":"143","author":"KA 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."},{"key":"9896_CR6","doi-asserted-by":"crossref","unstructured":"Behrisch, M., Hermann, M., Mengel, S., Salzer, G.: Give me another one! In: Elbassioni, K., Makino, K. (eds.) Proceedings 26th International Symposium on Algorithms and Computation (ISAAC 2015), Nagoya (Japan), Lecture Notes in Computer Science, vol. 9472, pp. 664\u2013676. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-48971-0_56"},{"key":"9896_CR7","doi-asserted-by":"crossref","unstructured":"Behrisch, M., Hermann, M., Mengel, S., Salzer, G.: As close as it gets. In: Kaykobad, M., Petreschi, R. (eds.) Proceedings 10th International Workshop on Algorithms and Computation (WALCOM 2016), Kathmandu (Nepal), Lecture Notes in Computer Science, vol. 9627, pp. 222\u2013235. Springer (2016)","DOI":"10.1007\/978-3-319-30139-6_18"},{"key":"9896_CR8","doi-asserted-by":"crossref","unstructured":"Behrisch, M., Hermann, M., Mengel, S., Salzer, G.: The next whisky bar. In: Kulikov, A.S., Woeginger, G.J. (eds.) Proceedings 11th International Computer Science Symposium in Russia (CSR 2016), St. Petersburg (Russia), Lecture Notes in Computer Science, vol. 9691, pp. 41\u201356. Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-34171-2_4"},{"issue":"1","key":"9896_CR9","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 Complex. Theory Column 43 35(1), 22\u201335 (2004)","journal-title":"SIGACT News Complex. Theory Column 43"},{"issue":"2","key":"9896_CR10","doi-asserted-by":"publisher","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."},{"key":"9896_CR11","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity classifications of Boolean constraint satisfaction problems. In: SIAM Monographs on Discrete Mathematics and Applications, vol. 7. SIAM, Philadelphia (2001)","DOI":"10.1137\/1.9780898718546"},{"issue":"7","key":"9896_CR12","doi-asserted-by":"publisher","first-page":"1103","DOI":"10.1016\/j.jcss.2008.02.005","volume":"74","author":"N Creignou","year":"2008","unstructured":"Creignou, N., Kolaitis, P.G., Zanuttini, B.: Structure identification of Boolean relations and plain bases for co-clones. J. Comput. Syst. Sci. 74(7), 1103\u20131115 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"9896_CR13","doi-asserted-by":"crossref","unstructured":"Creignou, N., Vollmer, H.: Boolean constraint satisfaction problems: when does post\u2019s lattice help? In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Complexity of Constraints\u2014An Overview of Current Research Themes [Result of a Dagstuhl Seminar], Lecture Notes in Computer Science, vol. 5250, pp. 3\u201337. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-92800-3_2"},{"issue":"1","key":"9896_CR14","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0304-3975(01)00146-3","volume":"288","author":"P Crescenzi","year":"2002","unstructured":"Crescenzi, P., Rossi, G.: On the Hamming distance of constraint satisfaction problems. Theor. Comput. Sci. 288(1), 85\u2013100 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9896_CR15","unstructured":"Dalal, M.: Investigations into a theory of knowledge base revision. In: Shrobe, H.E., Mitchell, T.M., Smith, R.G. (eds.) Proceedings 7th National Conference on Artificial Intelligence (AAAI-88), St. Paul (Minnesota, USA), pp. 475\u2013479. AAAI Press\/MIT Press (1988)"},{"issue":"1","key":"9896_CR16","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1109\/TIT.2002.806118","volume":"49","author":"I Dumer","year":"2003","unstructured":"Dumer, I., Micciancio, D., Sudan, M.: Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inf. Theory 49(1), 22\u201337 (2003)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1\u20133","key":"9896_CR17","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/BF01585160","volume":"62","author":"DS Hochbaum","year":"1993","unstructured":"Hochbaum, D.S., Megiddo, N., Naor, J., Tamir, A.: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Math. Program. 62(1\u20133), 69\u201383 (1993)","journal-title":"Math. Program."},{"issue":"1","key":"9896_CR18","first-page":"44","volume":"127","author":"JuI Janov","year":"1959","unstructured":"Janov, Ju.I., Mu\u010dnik, A.A.: \n                    \n                  , \n                    \n                   [Existence of k-valued closed classes without a finite basis]. Doklady Akademii Nauk SSSR 127(1), 44\u201346 (1959)","journal-title":"Doklady Akademii Nauk SSSR"},{"issue":"4","key":"9896_CR19","doi-asserted-by":"publisher","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."},{"key":"9896_CR20","doi-asserted-by":"crossref","unstructured":"Juban, L.: Dichotomy theorem for the generalized unique satisfiability problem. In: Ciobanu, G., P\u0103un, G. (eds.) Proceedings 12th Fundamentals of Computation Theory (FCT\u201999) Ia\u015fi (Romania), Lecture Notes in Computer Science, vol. 1684, pp. 327\u2013337. Springer, Berlin (1999)","DOI":"10.1007\/3-540-48321-7_27"},{"issue":"3","key":"9896_CR21","first-page":"317","volume":"1","author":"V Kann","year":"1994","unstructured":"Kann, V.: Polynomially bounded minimization problems that are hard to approximate. Nordic J. Comput. 1(3), 317\u2013331 (1994)","journal-title":"Nordic J. Comput."},{"issue":"6","key":"9896_CR22","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S Khanna","year":"2000","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM J. Comput. 30(6), 1863\u20131920 (2000)","journal-title":"SIAM J. Comput."},{"issue":"9","key":"9896_CR23","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1016\/j.ipl.2014.03.011","volume":"114","author":"V Lagerkvist","year":"2014","unstructured":"Lagerkvist, V.: Weak bases of Boolean co-clones. Inf. Process. Lett. 114(9), 462\u2013468 (2014)","journal-title":"Inf. Process. Lett."},{"key":"9896_CR24","volume-title":"Function Algebras on Finite Sets: A Basic Course of Many-Valued Logic and Clone Theory. Springer Monographs in Mathematics","author":"D Lau","year":"2006","unstructured":"Lau, D.: Function Algebras on Finite Sets: A Basic Course of Many-Valued Logic and Clone Theory. Springer Monographs in Mathematics. Springer, Berlin (2006)"},{"key":"9896_CR25","doi-asserted-by":"publisher","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)"},{"issue":"2","key":"9896_CR26","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF01069627","volume":"17","author":"BA Romov","year":"1981","unstructured":"Romov, B.A.: The algebras of partial functions and their invariants. Cybernetics 17(2), 157\u2013167 (1981). Translated from \n                    \n                  . Kibernetika 17(2), 1\u201311 (1981)","journal-title":"Cybernetics"},{"key":"9896_CR27","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings 10th Symposium on Theory of Computing (STOC\u201978), San Diego (California, USA), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"9896_CR28","doi-asserted-by":"crossref","unstructured":"Schnoor, H., Schnoor, I.: Partial polymorphisms and constraint satisfaction problems. In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Complexity of Constraints\u2014An Overview of Current Research Themes [Result of a Dagstuhl Seminar], Lecture Notes in Computer Science, vol. 5250, pp. 229\u2013254. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-92800-3_9"},{"key":"9896_CR29","unstructured":"Schnoor, I.: The Weak Base Method for Constraint Satisfaction. Dissertation, Gottfried Wilhelm Leibniz Universit\u00e4t Hannover (2008)"},{"key":"9896_CR30","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)"},{"issue":"6","key":"9896_CR31","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.641542","volume":"IT-43","author":"A Vardy","year":"1997","unstructured":"Vardy, A.: The intractability of computing the minimum distance of a code. IEEE Trans. Inf. Theory IT-43(6), 1757\u20131766 (1997)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"9896_CR32","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S Warshall","year":"1962","unstructured":"Warshall, S.: A theorem on Boolean matrices. J. Assoc. Comput. Mach. 9(1), 11\u201312 (1962)","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9896-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9896-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9896-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,19]],"date-time":"2019-12-19T19:07:42Z","timestamp":1576782462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9896-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,20]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["9896"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9896-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2018,12,20]]},"assertion":[{"value":"20 December 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}