Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PATTERN MATCHING:
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