Definability and Compression
Consider compression schemas on strings and images as finite structures $U$,
in particular the classical Ziv-Lempel universal compression.
We look at the compressed structures as finite structures $U_{ZL}$ and
ask the following question :
Given a first-order query $Q$ in the language of $U$, can we find an
equivalent $Q_{ZL}$ in the language of $U_{ZL}$ ?
This question is motivated by the multimedia databases which deal with compressed
data (such as images). We just ask if it possible to query such databases
without decompressing the data.
We will answer this question for various compression schemas. For the classical
Ziv-Lempel, the answer is negative but we will isolate a fragment of the first-order
queries where the answer is positive.