Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2003

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: string compression

Sortuj według:

Ogranicz wyniki do:

Definability and Compression

Afrati F., Leiß H., Rougemont M. de

Fundamenta Informaticae

2003

Vol. 56, nr 1,2

155-180

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 L, 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.