  We consider the problem of {\em restructuring} compressed texts without
explicit decompression. We present algorithms which allow conversions from
compressed representations of a string $T$ produced by any grammar-based
compression algorithm, to representations produced by several specific
compression algorithms including LZ77, LZ78, run length encoding, and some
grammar based compression algorithms. These are the first algorithms that
achieve running times polynomial in the size of the compressed input and output
representations of $T$. Since most of the representations we consider can
achieve exponential compression, our algorithms are theoretically faster in the
worst case, than any algorithm which first decompresses the string for the
conversion.
