Automata on Lempel-ziv Compressed Strings. Export

@inproceedings{citeulike:265969, abstract = {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.}, author = {Lei{\ss}, Hans and de Rougemont, Michel}, booktitle = {CSL 2003}, citeulike-article-id = {265969}, editor = {Baaz, Matthias and Makowsky, Johann A.}, keywords = {automata, compression}, pages = {384--396}, posted-at = {2005-07-27 05:50:11}, priority = {3}, title = {Automata on Lempel-ziv Compressed Strings.}, volume = {2803}, year = {2003} }

TY - CONF ID - citeulike:265969 L3 - citeulike-article-id:265969 N2 - 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. EP - 396 TI - Automata on Lempel-ziv Compressed Strings. VL - 2803 T2 - CSL 2003 SP - 384 KW - automata KW - compression AU - Leiß, Hans AU - de Rougemont, Michel A2 - Baaz, Matthias A2 - Makowsky, Johann PY - 2003/// ER -