In this article, we present an application of a simple technique of local recompression,
previously developed by the author in the context algorithms for compressed strings [Jeż …

In this paper, we study the fundamental problem of maintaining a dynamic collection of
strings under the following operations:• make_string–add a string of constant length,• concat …

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 …

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

Given two positions $ i $ and $ j $ in a string $ T $ of length $ N $, a longest common
extension (LCE) query asks for the length of the longest common prefix between suffixes …

Grammar-Based Tree Compression Page 1 Grammar-Based Tree Compression Markus
Lohrey(B) Universität Siegen, Siegen, Germany lohrey@eti.uni-siegen.de Abstract. This paper …

We revisit tree compression with top trees (Bille et al.[2]), and present several improvements
to the compressor and its analysis. By significantly reducing the amount of information stored …

Miller and Reif's FOCS'85 classic and fundamental tree contraction algorithm is a broadly
applicable technique for the parallel solution of a large number of tree problems …

Contexts are terms with one 'hole', ie a place in which we can substitute an argument. In
context unification we are given an equation over terms with variables representing contexts …