{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T16:36:00Z","timestamp":1648571760225},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2014,7,9]],"date-time":"2014-07-09T00:00:00Z","timestamp":1404864000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2014,9]]},"abstract":"<jats:p>We resolve a conjecture proposed by D.E. Knuth concerning a recurrence arising in the satisfiability problem. Knuth's recurrence resembles recurrences arising in the analysis of tries, in particular PATRICIA tries, and asymmetric leader election. We solve Knuth's recurrence exactly and asymptotically, using analytic techniques such as the Mellin transform and analytic depoissonization.<\/jats:p>","DOI":"10.1017\/s0963548314000133","type":"journal-article","created":{"date-parts":[[2014,7,9]],"date-time":"2014-07-09T13:37:29Z","timestamp":1404913049000},"page":"829-841","source":"Crossref","is-referenced-by-count":1,"title":["A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence"],"prefix":"10.1017","volume":"23","author":[{"given":"PHILIPPE","family":"JACQUET","sequence":"first","affiliation":[]},{"given":"CHARLES","family":"KNESSL","sequence":"additional","affiliation":[]},{"given":"WOJCIECH","family":"SZPANKOWSKI","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,7,9]]},"reference":[{"key":"S0963548314000133_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00002-E"},{"key":"S0963548314000133_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032770"},{"key":"S0963548314000133_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00167-9"},{"key":"S0963548314000133_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/0406016"},{"key":"S0963548314000133_ref12","unstructured":"Sedgewick R. personal communication."},{"key":"S0963548314000133_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/96559.214080"},{"key":"S0963548314000133_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90110-7"},{"key":"S0963548314000133_ref1","first-page":"394","article-title":"A machine program for theorem proving.","volume":"5","author":"Davis","year":"1962","journal-title":"Comm. Assoc. Comput. Mach."},{"key":"S0963548314000133_ref8","doi-asserted-by":"crossref","DOI":"10.37236\/1302","article-title":"Analysis of an asymmetric leader election algorithm","volume":"4","author":"Janson","year":"1997","journal-title":"Electron. J. Combin."},{"key":"S0963548314000133_ref5","unstructured":"Goldberg A. (1979) On the complexity of the satisfiability problem. Courant Computer Science Report no. 16, New York University."},{"key":"S0963548314000133_ref9","volume-title":"The Art of Computer Programming: Sorting and Searching","author":"Knuth","year":"1998"},{"key":"S0963548314000133_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"S0963548314000133_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S0001867800015846"},{"key":"S0963548314000133_ref10","unstructured":"Knuth D. E. personal communication."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,22]],"date-time":"2020-08-22T03:26:44Z","timestamp":1598066804000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000133\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,9]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["S0963548314000133"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000133","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,9]]}}}