## Paper: Definability and Compression (at LICS 2000)

**Foto N. Afrati Hans Leiß Michel de Rougemont**

### Abstract

A compression algorithm takes a finite structure of a class K as input and produces a finite structure of a different class K' as output. Given a property P on the class K defined in a logic {cal L}, we study the definability of property P on the class K'. We consider two compression schemas on unary ordered structures (words), compression by run-length encoding and the classical Lempel-Ziv.First-order properties of strings are first-order on run-length compressed strings, but this fails for images, i.e. 2-dimensional strings. We present simple first-order properties of strings which are not first-order definable on strings compressed with the Lempel-Ziv compression schema.We show that all properties of strings that are first-order definable on strings are definable on Lempel-Ziv compressed strings in FO (TC), the extension of first-order logic with the transitive closure operator. We define a subclass cal F of the first-order properties of strings such that if L is defined by a property in cal F, it is also first-order definable on the Lempel-Ziv compressed strings. Monadic second-order properties of strings are dyadic second order definable on Lempel-Ziv compressed strings.

### BibTeX

@InProceedings{AfratiLeideRougemon-DefinabilityandComp, author = {Foto N. Afrati and Hans Leiß and Michel de Rougemont}, title = {Definability and Compression}, booktitle = {Proceedings of the Fifteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2000)}, year = {2000}, month = {June}, pages = {63--73}, location = {Santa Barbara, CA, USA}, publisher = {IEEE Computer Society Press} }