4 citations · 6 across the 4 of their papers we have counts for
5 papers · 1 filter
Hidden Words Statistics for Large Patterns
Svante Janson, Wojciech Szpankowski
We study here the so called subsequence pattern matching also known as hidden pattern matching in which one searches for a given pattern of length as a subsequence in a ran…
Asymmetric Rényi Problem
Michael Drmota, Abram Magner, Wojciech Szpankowski
In 1960 Rényi in his Michigan State University lectures asked for the number of random queries necessary to recover a hidden bijective labeling of distinct objects. In each que…
Asymmetric Rényi Problem and PATRICIA Tries
Michael Drmota, Abram Magner, Wojciech Szpankowski
In 1960, Rényi asked for the number of random queries necessary to recover a hidden bijective labeling of n distinct objects. In each query one selects a random subset of labels an…
A Limit Theorem for Radix Sort and Tries with Markovian Input
Kevin Leckey, Ralph Neininger, Wojciech Szpankowski
Tries are among the most versatile and widely used data structures on words. In particular, they are used in fundamental sorting algorithms such as radix sort which we study in thi…
Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model
Kevin Leckey, Ralph Neininger, Wojciech Szpankowski
Tries are among the most versatile and widely used data structures on words. They are pertinent to the (internal) structure of (stored) words and several splitting procedures used…