33 Result(s)
-
Chapter and Conference Paper
Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction
We study the query complexity of exactly reconstructing a string from adaptive queries, such as substring, subsequence, and jumbled-index queries. Such problems have applications, e.g., in computational biolog...
-
Chapter and Conference Paper
Approximating the Anticover of a String
The k-anticover of a string S is a set of distinct k-length substrings such that every index in S is contained in one of these substrings. The existence of an anticover indicates a lack of structure in S. It was ...
-
Chapter and Conference Paper
Multidimensional Period Recovery
Multidimensional data are widely used in real-life applications. Intel’s new brand of SSDs, called 3D XPoint, is an example of three-dimensional data. Motivated by a structural analysis of multidimensional dat...
-
Chapter and Conference Paper
Searching for a Modified Pattern in a Changing Text
Much attention has been devoted recently to the dynamic model of pattern matching. In this model the input is updated or changed locally. One is interested in obtaining the appropriate search result in time th...
-
Chapter and Conference Paper
Longest Common Factor After One Edit Operation
It is well known that the longest common factor (LCF) of two strings over an integer alphabet can be computed in time linear in the total length of the two strings. Our aim here is to present an algorithm that...
-
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
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 Hardness of Jumbled Indexing
Jumbled indexing is the problem of indexing a text T for queries that ask whether there is a substring of T matching a pattern represented as a Parikh vector, i.e., the vector of frequency counts for each charact...
-
Chapter
Hypertext Searching - A Survey
The idea of hypertext has been successfully used in Jewish literature. Its importance has been steadily growing over the last two decades. Internet and other information systems use hypertext format, with data...
-
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
Consensus Optimizing Both Distance Sum and Radius
The consensus string problem is finding a representative string (consensus) of a given set \(\mathbb{S}\) of strings. I...
-
Chapter and Conference Paper
Towards a Theory of Patches
Many applications have a need for indexing unstructured data. It turns out that a similar ad-hoc method is being used in many of them - that of considering small particles of the data.
-
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
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, ...
