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 Program Social Program Registration Location and Venue Accommodation Committees Contact Colocated Events Authors' instructions

Print 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