Abstract
Tight connections between leafs languages and strings compressed
via straight-line programs (SLPs) are established. It is shown
that the compressed membership problem for a language $L$ is complete
for the leaf language class defined by $L$ via logspace machines.
A more difficult variant of the compressed membership problem for
$L$ is shown to be complete for the leaf language class defined
by $L$ via polynomial time machines. As a corollary,
a fixed linear visibly pushdown language with
a PSPACE-complete compressed membership problem is obtained.
For XML languages,
the compressed membership problem is shown to be coNP-complete.
BibTeX - Entry
@InProceedings{lohrey:LIPIcs:2008:1761,
author = {Markus Lohrey},
title = {{Leaf languages and string compression}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {292--303},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-08-8},
ISSN = {1868-8969},
year = {2008},
volume = {2},
editor = {Ramesh Hariharan and Madhavan Mukund and V Vinay},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1761},
URN = {urn:nbn:de:0030-drops-17612},
doi = {10.4230/LIPIcs.FSTTCS.2008.1761},
annote = {Keywords: Leaf languages, string compression, grammar-based compression, complexity theory}
}
|
Keywords: |
|
Leaf languages, string compression, grammar-based compression, complexity theory |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
|
Issue Date: |
|
2008 |
|
Date of publication: |
|
05.12.2008 |
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)