Definability and Compression
Foto Afrati, Hans Leiß, Michel de Rougemont · 2002
. We study the rst-order denability on compressed structures of properties of strings and images. Simple rst-order properties of strings are presented which are not rst-order de- nable on strings compressed with the Lempel-Ziv compression schema. Conversely, there are properties that are rst-order denable on Lempel-Ziv compressed strings, but not on strings. We show that all properties of strings that are rst-order denable on strings are denable on Lempel-Ziv compressed strings in an extension of rst-order logic by a transitive closure operator. We dene a subclass C of the rst-order properties of strings such that if L is dened by a property in C, it is also rst-order denable on the Lempel-Ziv compressed strings. We also consider a naive compression schema where all rst-order properties of strings are rstorder denable on compressed strings, but where this fails for 2-dimensional strings (images). 1 Introduction A classical search problem on strings asks fo...