Computer Science Logic and 8th Kurt Gödel Colloquium
Hans Leiss, Michel de Rougemont: Automata on Lempel-Ziv-compressed strings
Welcome and News
Host Institutions
Calls and Deadlines
Social Program
Location and Venue
Colocated Events
Authors' instructions
Print current pagePrint this page
We consider the 'compressed model checking problem': which properties of strings can be determined from a compressed version of the string, without decompression?

Using the Lempel-Ziv-78 compression algorithm to compress a string yields a dictionary of substrings, i.e. an edge-labelled tree with an order-compatible enumeration, here called an LZ-trie. Queries about strings translate to queries about LZ-tries and hence can in principle be answered without decompression. We compare notions of automata accepting LZ-tries and consider the relation between acceptable and monadic-second-order-definable classes of LZ-tries. It turns out that regular properties of strings can be checked efficiently on compressed strings by LZ-trie automata.
© 2002-2003 Kurt Gödel Society, Norbert Preining. 2003-06-04 Valid HTML 4.01! Valid CSS! Debian