Paper: Definability and Compression (at LICS 2000)

Authors: 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}
  }