Affiliations: National Technical University, Athens, Greece | Universität München, CIS, D-80538 München, Germany | LRI, Bâtiment 490, Université Paris-Sud,
F-91405 Orsay Cedex, France
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 ℒ, we study the definability of property P on the class K'. We consider two compression schemes on unary ordered structures (strings),
compression by run-length encoding and the classical Lempel-Ziv-78 scheme.
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-78 compression scheme. 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 F of
the first-order properties of strings such that if P is a property in F, it is also first-order definable on the Lempel-Ziv compressed strings. Monadic second-order properties of strings, i.e. regular languages, are dyadic
second-order definable on Lempel-Ziv compressed strings.
