Leaf languages and string compression
Leaf languages and string compression
复制标题
叶语言和字符串压缩
DOI：
10.1016/j.ic.2011.01.009
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Markus Lohrey
中科院分区：
文献类型：
--
作者：
Markus Lohrey
叶语言和直线程序（SLP）压缩的字符串之间建立了紧密的联系。结果表明，对于由 Lvia logspace 机定义的叶语言类，语言的压缩成员资格问题是完整的。 Li 的压缩成员资格问题的一个更困难的变体被证明对于由 Lvia 多项式时间机定义的叶语言类是完整的。作为推论，证明存在一种固定的线性可见下推语言，其压缩隶属问题是 PSPACE 完全的。对于XML语言，它表明压缩成员资格问题是coNP完全的。此外，它表明SLP压缩字符串的嵌入问题对于PP（概率多项式时间）来说是困难的。
Tight connections between leaf languages and strings compressed by straight-line programs (SLPs) are established. It is shown that the compressed membership problem for a languageLis complete for the leaf language class defined byLvia logspace machines. A more difficult variant of the compressed membership problem forLis shown to be complete for the leaf language class defined byLvia polynomial time machines. As a corollary, it is shown that there exists a fixed linear visibly pushdown language for which the compressed membership problem is PSPACE-complete. For XML languages, it is shown that the compressed membership problem is coNP-complete.Furthermore it is shown that the embedding problem for SLP-compressed strings is hard for PP (probabilistic polynomial time).