Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

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 >>>

Sandip Sinha, Omri Weinstein

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 >>>

Omri Ben-Eliezer

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 >>>