
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 LempelZiv78 compression algorithm to compress a string yields a dictionary of substrings, i.e. an edgelabelled tree with an ordercompatible enumeration, here called an LZtrie. Queries about strings translate to queries about LZtries and hence can in principle be answered without decompression. We compare notions of automata accepting LZtries and consider the relation between acceptable and monadicsecondorderdefinable classes of LZtries. It turns out that regular properties of strings can be checked efficiently on compressed strings by LZtrie automata.
© 20022003 Kurt Gödel Society, Norbert Preining. 
20030604
 