Wyszukiwarka
Abstrakt
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.
Cytowania
-
1
CrossRef
-
0
Web of Science
-
2
Scopus
Autorzy (3)
-
Philippe Jacquet
- Bell Labs, Alcatel-Lucent .
-
Charles Knessel
- University of Illinois at Chicago Department of Mathematics, Statistics, and Computer Scien
-
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
COMBINATORICS PROBABILITY & COMPUTING
nr 23,
wydanie 05,
strony 829 - 841,
ISSN: 0963-5483 - Język:
- angielski
- Rok wydania:
- 2014
- Opis bibliograficzny:
- 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:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1017/s0963548314000133
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 106 razy
Publikacje, które mogą cię zainteresować
On Symmetry of Uniform and Preferential Attachment Graphs
- A. Magner,
- S. Janson,
- G. Kollias
- + 1 autorów
2014