{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:25:25Z","timestamp":1725513925795},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540727873"},{"type":"electronic","value":"9783540727880"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72788-0_11","type":"book-chapter","created":{"date-parts":[[2007,6,28]],"date-time":"2007-06-28T08:25:22Z","timestamp":1183019122000},"page":"80-93","source":"Crossref","is-referenced-by-count":2,"title":["Horn Upper Bounds and Renaming"],"prefix":"10.1007","author":[{"given":"Marina","family":"Langlois","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert H.","family":"Sloan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\u00f6rgy","family":"Tur\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0196-6774(80)90007-3","volume":"1","author":"B. Aspvall","year":"1980","unstructured":"Aspvall, B.: Recognizing disguised NR(1) instances of the satisfiability problem. Journal of Algorithms\u00a01, 97\u2013103 (1980)","journal-title":"Journal of Algorithms"},{"key":"11_CR2","unstructured":"Bollob\u00e1s, B., Kohayakawa, Y., \u0141uczak, T.: On the evolution of random Boolean functions. In: Frankl, P., et al. (eds.) Extremal Problems for Finite Sets (Visegr\u00e1d). Bolyai Society Mathematical Studies, vol.\u00a03, pp. 137\u2013156. J\u00e1nos Bolyai Mathematical Society, Budapest (1994)"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0166-218X(99)00031-1","volume":"96-97","author":"E. Boros","year":"1999","unstructured":"Boros, E.: Maximum renamable Horn sub-CNFs. Discrete Appl.\u00a0Math.\u00a096-97, 29\u201340 (1999)","journal-title":"Discrete Appl.\u00a0Math."},{"key":"11_CR4","unstructured":"Boufkhad, Y.: Algorithms for propositional KB approximation. In: Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98) and of the 10th Conference on Innovative Applications of Artificial Intelligence (IAAI-98), pp. 280\u2013285 (1998)"},{"issue":"3\u20134","key":"11_CR5","first-page":"137","volume":"10","author":"M. Cadoli","year":"1997","unstructured":"Cadoli, M., Donini, F.M.: A survey on knowledge compilation. AI Communications\u00a010(3\u20134), 137\u2013150 (1997)","journal-title":"AI Communications"},{"issue":"3","key":"11_CR6","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0166-218X(96)00028-5","volume":"75","author":"Y. Crama","year":"1997","unstructured":"Crama, Y., Ekin, O., Hammer, P.L.: Variable and term removal from Boolean formulae. Discrete Applied Mathematics\u00a075(3), 217\u2013230 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR7","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1613\/jair.989","volume":"17","author":"A. Darwiche","year":"2002","unstructured":"Darwiche, A., Marquis, P.: A knowledge compilation map. Journal of Artificial Intelligence Research\u00a017, 229\u2013264 (2002)","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"1-2","key":"11_CR8","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.artint.2004.01.003","volume":"162","author":"A. Val del","year":"2005","unstructured":"del Val, A.: First order LUB approximations: characterization and algorithms. Artificial Intelligence\u00a0162(1-2), 7\u201348 (2005)","journal-title":"Artificial Intelligence"},{"key":"11_CR9","first-page":"17","volume":"5","author":"P. Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci\u00a05, 17\u201361 (1960)","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"14","DOI":"10.2307\/2268661","volume":"16","author":"A. Horn","year":"1951","unstructured":"Horn, A.: On sentences which are true on direct unions of algebras. J. Symbolic Logic\u00a016, 14\u201321 (1951)","journal-title":"J. Symbolic Logic"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M.R. Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theor.\u00a0Comput.\u00a0Sci.\u00a043, 169\u2013188 (1986)","journal-title":"Theor.\u00a0Comput.\u00a0Sci."},{"key":"11_CR12","unstructured":"Kautz, H., Selman, B.: An empirical evaluation of knowledge compilation by theory approximation. In: Proceedings of the 12th National Conference on Artificial Intelligence, pp. 155\u2013161 (1994)"},{"key":"11_CR13","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An Introduction to Computational Learning Theory","author":"M.J. Kearns","year":"1994","unstructured":"Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press, Cambridge (1994)"},{"key":"11_CR14","unstructured":"Langlois, M., Sloan, R.H., Tur\u00e1n, G.: Horn upper bounds of random 3-CNF: A computational study. In: Ninth Int. Symp. Artificial Intelligence and Mathematics (2006), Available on-line from URL \n                  \n                    http:\/\/anytime.cs.umass.edu\/aimath06\/"},{"key":"11_CR15","first-page":"23","volume":"36","author":"A.A. Levin","year":"1981","unstructured":"Levin, A.A.: Comparative complexity of disjunctive normal forms (in Russian). Metody Discret. Analiz.\u00a036, 23\u201338 (1981)","journal-title":"Metody Discret. Analiz."},{"key":"11_CR16","first-page":"134","volume":"25","author":"H.R. Lewis","year":"1978","unstructured":"Lewis, H.R.: Renaming a set of clauses as a Horn set. J.\u00a0ACM\u00a025, 134\u2013135 (1978)","journal-title":"J.\u00a0ACM"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"61","DOI":"10.2307\/2268172","volume":"8","author":"J.C.C. McKinsey","year":"1943","unstructured":"McKinsey, J.C.C.: The decision problem for some classes without quantifiers. J. Symbolic Logic\u00a08, 61\u201376 (1943)","journal-title":"J. Symbolic Logic"},{"key":"11_CR18","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1103\/PhysRevE.66.056126","volume":"66","author":"M. M\u00e9zard","year":"2002","unstructured":"M\u00e9zard, M., Zecchina, R.: The random K-satisfiability problem: from an analytic solution to an efficient algorithm. Physical Review E\u00a066, 56\u2013126 (2002)","journal-title":"Physical Review E"},{"key":"11_CR19","unstructured":"Mora, T., M\u00e9zard, M., Zecchina, R.: Pairs of SAT assignments and clustering in random Boolean formulae. Submitted to Theoretical Computer Science (2005), available from URL \n                  \n                    http:\/\/www.citebase.org\/cgi-bin\/citations?id=oai:arXiv.org:cond-mat\/0506053"},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(94)00092-1","volume":"82","author":"D. Roth","year":"1996","unstructured":"Roth, D.: On the hardness of approximate reasoning. Artificial Intelligence\u00a082, 273\u2013302 (1996)","journal-title":"Artificial Intelligence"},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science","first-page":"121","volume-title":"Principles and Practice of Constraint Programming - CP 2001","author":"M.Y. Vardi","year":"2001","unstructured":"Vardi, M.Y., Aguirre, A.S.M.: Random 3-SAT and BDDs: The Plot Thickens Further. In: Walsh, T. (ed.) CP 2001. LNCS, vol.\u00a02239, pp. 121\u2013136. Springer, Heidelberg (2001)"},{"key":"11_CR22","first-page":"193","volume":"43","author":"B. Selman","year":"1996","unstructured":"Selman, B., Kautz, H.: Knowledge compilation and theory approximation. J.\u00a0ACM\u00a043, 193\u2013224 (1996)","journal-title":"J.\u00a0ACM"},{"key":"11_CR23","unstructured":"Sloan, R.H., Sz\u00f6r\u00e9nyi, B., Tur\u00e1n, G.: On k-term DNF with the maximal number of prime implicants. Submitted for publication. Preliminary version available as Electronic Colloquium on Computational Complexity (ECCC) Technical Report TR05-023, available on-line at \n                  \n                    http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"11_CR24","volume-title":"Effective Logic Computation","author":"K. Truemper","year":"1998","unstructured":"Truemper, K.: Effective Logic Computation. Wiley-Interscience, Chichester (1998)"},{"key":"11_CR25","series-title":"Lecture Notes in Computer Science","first-page":"135","volume-title":"Theory and Applications of Satisfiability Testing","author":"L. Norden van","year":"2004","unstructured":"van Norden, L., van Maaren, H.: Hidden Threshold Phenomena for Fixed-Density SAT-formulae. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 135\u2013149. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72788-0_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:05:02Z","timestamp":1605744302000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72788-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540727873","9783540727880"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72788-0_11","relation":{},"subject":[]}}