Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Pattern Matching:
TR95-022 | 2nd May 1995
Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

Pattern-Matching for Strings with Short Descriptions

We consider strings which are succinctly described. The description
is in terms of straight-line programs in which the constants are
symbols and the only operation is the concatenation. Such
descriptions correspond to the systems of recurrences or to
context-free grammars generating single words. The descriptive ... more >>>

TR18-141 | 6th August 2018
Sandip Sinha, Omri Weinstein

Local Decodability of the Burrows-Wheeler Transform

Revisions: 1

The Burrows-Wheeler Transform (BWT) is among the most influential discoveries in text compression and DNA storage. It is a \emph{reversible} preprocessing step that rearranges an $n$-letter string into runs of identical characters (by exploiting context regularities), resulting in highly compressible strings, and is the basis for the ubiquitous \texttt{bzip} program. ... more >>>

TR18-196 | 19th November 2018
Omri Ben-Eliezer

Testing local properties of arrays

We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of $d$-dimensional arrays $f:[n]^d \to \Sigma$ is $k$-local if it can be defined by a family of $k \times \ldots \times k$ forbidden consecutive patterns. This definition captures numerous interesting properties. For example, monotonicity, Lipschitz continuity and ... more >>>

ISSN 1433-8092 | Imprint