Combinatorial Pattern Matching
21st Annual Symposium, CPM 2010, New York, NY, USA, June 21-23, 2010. Proceedings
Chapter and Conference Paper
The Range LCP problem is to preprocess a string \(S[1\dots n]\) , to enable efficient solutions of the following query: given a ...
Chapter and Conference Paper
Vertex Relabeling is a variant of the graph relabeling problem. In this problem, the input is a graph and two vertex labelings, and the question is to determine how close are the labelings. The distance measur...
Chapter and Conference Paper
The dictionary matching with gaps problem is to preprocess a dictionary D of d gapped patterns P 1,…,P d over alphabet Σ, where each gapped pattern P ...
Chapter and Conference Paper
Jumbled Indexing, the problem of indexing a text for histogram queries, has been of much interest lately. In this paper we consider jumbled indexing for run-length encoded texts. We refute a form...
Chapter and Conference Paper
The Consensus String Problem is that of finding a string, such that the maximum Hamming distance from it to a given set of strings of the same length is minimized. However, a generalization is necessary for clust...
Chapter and Conference Paper
Palindrome recognition is a classic problem in computer science. It is an example of a language that can not be recognized by a deterministic finite automaton and is often brought as an example of a problem wh...
Chapter and Conference Paper
Periodicity has been historically well studied and has numerous applications. In nature, however, few cyclic phenomena have an exact period.
Chapter and Conference Paper
The Closest String Problem is defined as follows. Let S be a set of k strings {s 1,…s k }, each of length ℓ, find a string
Chapter and Conference Paper
The problem of finding the consensus of a given set of strings is formally defined as follows: given a set of strings S = {s 1,…s k }, and ...
Chapter and Conference Paper
The Shortest Common Supersequence (SCS) is the problem of seeking a shortest possible sequence that contains each of the input sequences as a subsequence. In this paper we consider applying the problem to Positio...
Book and Conference Proceedings
21st Annual Symposium, CPM 2010, New York, NY, USA, June 21-23, 2010. Proceedings
Chapter and Conference Paper
The Square Tiling Problem was recently introduced as equivalent to the problem of reconstructing an image from patches and a possible general-purpose indexing tool. Unfortunately, the Square Tiling Problem was...
Chapter and Conference Paper
A string S ∈ Σ m can be viewed as a set of pairs $\{ (s_i , i) \mid s_i\in S,\ i\in \{ 0,\ldots, m-...
Chapter
A basic assumption in traditional pattern matching is that the order of the elements in the given input strings is correct, while the description of the content, i.e. the description of the elements, may be er...
Chapter and Conference Paper
In this paper, the optimality proof of Lempel-Ziv coding is re-studied, and a much more general compression optimality theorem is derived. In particular, the property of quasi-distinct parsing is defined. This pr...
Chapter and Conference Paper
A string S ∈ Σ m can be viewed as a set of pairs S = { (σ i , i) : i ∈ { 0,..., m − 1} }. We consider approx...
Chapter and Conference Paper
We consider the two-dimensional Range Minimum Query problem: for a static (m ×n)-matrix of size N = mn which may be preprocessed, answer on-line queries of the form “where is the position of a minimum element in ...
Chapter and Conference Paper
In this paper a deterministic algorithm for the length reduction problem is presented. This algorithm enables a new tool for performing fast convolution in sparse data. The proposed algorithm performs the conv...
Chapter and Conference Paper
This paper introduces a new pattern matching model that has been gaining importance recently, that of Asynchronous Pattern Matching. Traditional pattern matching has assumed the possibility of errors in the data
Chapter and Conference Paper
The rapidly growing need for analysis of digitized images in multimedia systems has lead to a variety of interesting problems in multidimensional pattern matching. One of the problems is that of scaled matching, ...