Two decades ago, a breakthrough in indexing string collections made it possible to
represent them within their compressed space while at the same time offering indexed …

We introduce new type of context-free grammars, AVL-grammars, and show their
applicability to grammar-based compression. Using this type of grammars we present O (n …

Rank minimization problem can be boiled down to either Nuclear Norm Minimization (NNM)
or Weighted NNM (WNNM) problem. The problems related to NNM (or WNNM) can be …

Results on algorithmic problems on strings that are given in a compressed form via straight-
line programs are surveyed. A straight-line program is a context-free grammar that …

A string graph is the intersection graph of a set of curves in the plane. Each curve is
represented by a vertex, and an edge between two vertices means that the corresponding …

In this article, a fully compressed pattern matching problem is studied. The compression is
represented by straight-line programs (SLPs)—that is, context-free grammars generating …

In this paper we present a simple linear-time algorithm constructing a context-free grammar
of size O (g log⁡(N/g)) for the input string, where N is the size of the input string and g the …

We introduce a general framework which is suitable to capture the essence of compressed
pattern matching according to various dictionary-based compressions. It is a formal system …

What kind of operations can we perform effectively (without full unpacking) with compressed
texts? In this paper we consider three fundamental problems:(1) check the equality of two …

The study of computational problems in combinatorial group theory goes back more than
100 years. In a seminal paper from 1911, Max Dehn posed three decision problems [46]: the …