Search
Abstract
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.
Citations
-
1
CrossRef
-
0
Web of Science
-
2
Scopus
Authors (3)
-
Philippe Jacquet
- Bell Labs, Alcatel-Lucent .
-
Charles Knessel
- University of Illinois at Chicago Department of Mathematics, Statistics, and Computer Scien
-
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
COMBINATORICS PROBABILITY & COMPUTING
no. 23,
edition 05,
pages 829 - 841,
ISSN: 0963-5483 - Language:
- English
- Publication year:
- 2014
- Bibliographic description:
- Jacquet P., Knessel C., Szpankowski W.: A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence// COMBINATORICS PROBABILITY & COMPUTING. -Vol. 23, iss. 05 (2014), s.829-841
- DOI:
- Digital Object Identifier (open in new tab) 10.1017/s0963548314000133
- Verified by:
- Gdańsk University of Technology
seen 106 times
Recommended for you
On Symmetry of Uniform and Preferential Attachment Graphs
- A. Magner,
- S. Janson,
- G. Kollias
- + 1 authors
2014