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.
Autorzy
- Philippe Jacquet,
- Charles Knessel,
- prof. dr inż. Wojciech Szpankowski link otwiera się w nowej karcie
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1017/s0963548314000133
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie wyróżnionym w JCR
- Język
- angielski
- Rok wydania
- 2014
Źródło danych: MOSTWiedzy.pl - publikacja "A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence" link otwiera się w nowej karcie
