A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence - Publikacja - MOST Wiedzy

Wyszukiwarka

A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence

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

  • 1

    Web of Science

  • 2

    Scopus

Autorzy (3)

  • Zdjęcie użytkownika  Philippe Jacquet

    Philippe Jacquet

    • Bell Labs, Alcatel-Lucent .
  • Zdjęcie użytkownika  Charles Knessel

    Charles Knessel

    • University of Illinois at Chicago Department of Mathematics, Statistics, and Computer Scien
  • Zdjęcie użytkownika prof. dr inż. Wojciech Szpankowski

    Wojciech Szpankowski prof. dr inż.

    • Purdue University, W. Lafayette Department of Computer Science

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 17 razy

Publikacje, które mogą cię zainteresować

Meta Tagi