10.4230/LIPICS.FSTTCS.2008.1761
Lohrey, Markus
Markus
Lohrey
Leaf languages and string compression
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Leaf languages
string compression
grammar-based compression
complexity theory
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
2008
2008-12-05
2008-12-05
2008-12-05
en
urn:nbn:de:0030-drops-17612
10.4230/LIPIcs.FSTTCS.2008
978-3-939897-08-8
1868-8969
10.4230/LIPIcs.FSTTCS.2008
LIPIcs, Volume 2, FSTTCS 2008
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
2
25
292
303
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
2
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
442770 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 292-303