26 Result(s)
within
Chapter
Conference Paper
Amihood Amir
Pattern Recognition
-
Chapter and Conference Paper
Range LCP Queries Revisited
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
On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling
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
Dictionary Matching with One Gap
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
Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on Run-Length Encoded Strings
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
On the Efficiency of the Hamming C-Centerstring Problems
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
Approximate On-line Palindrome Recognition, and Applications
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
Approximate Period Detection and Correction
Periodicity has been historically well studied and has numerous applications. In nature, however, few cyclic phenomena have an exact period.
-
Chapter and Conference Paper
Configurations and Minority in the String Consensus Problem
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
Approximations and Partial Solutions for the Consensus Sequence Problem
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
Weighted Shortest Common Supersequence
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...
-
Chapter and Conference Paper
A PTAS for the Square Tiling Problem
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
Approximate String Matching with Stuck Address Bits
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 and Conference Paper
Quasi-distinct Parsing and Optimal Compression Methods
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
Approximate String Matching with Address Bit Errors
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
Two-Dimensional Range Minimum Queries
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
Deterministic Length Reduction: Fast Convolution in Sparse Data and Applications
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
Asynchronous Pattern Matching
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
Faster Two Dimensional Scaled Matching
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, ...
-
Chapter and Conference Paper
Approximate Matching in Weighted Sequences
Weighted sequences have been recently introduced as a tool to handle a set of sequences that are not identical but have many local similarities. The weighted sequence is a “statistical image” of this set, wher...
-
Chapter and Conference Paper
Property Matching and Weighted Matching
Pattern Matching with Properties (Property Matching, for short), involves a string matching between the pattern and the text, and the requirement that the text part satisfies some property.
