首页> 外文会议>Foundations of software science and computational structures >Parameter Reduction in Grammar-Compressed Trees
【24h】

Parameter Reduction in Grammar-Compressed Trees

机译:语法压缩树中的参数约简

获取原文
获取原文并翻译 | 示例

摘要

Trees can be conveniently compressed with linear straight-line context-free tree grammars. Such grammars generalize straight-line context-free string grammars which are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression). It is shown that every linear straight-line context-free tree grammar can be transformed in polynomial time into a monadic (and linear) one. A tree grammar is monadic if each nonterminal uses at most one context parameter. Based on this result, a polynomial time algorithm is presented for testing whether a given nondeter-ministic tree automaton with sibling constraints accepts a tree given by a linear straight-line context-free tree grammar. It is shown that if tree grammars are non-deterministic or non-linear, then reducing their numbers of parameters cannot be done without an exponential blow-up in grammar size.
机译:可以使用线性直线上下文无关的树语法方便地压缩树。这样的语法概括了无上下文上下文的直线字符串语法,该语法广泛用于直接在压缩结构上执行(无需事先解压缩)的算法。结果表明,每一个线性直线的上下文无关树语法都可以在多项式时间内转化为单子(和线性)形式。如果每个非终结符最多使用一个上下文参数,则树语法是单子语法。基于该结果,提出了多项式时间算法,用于测试具有同级约束的给定非确定性树自动机是否接受线性直线上下文无关树语法给出的树。结果表明,如果树语法不是确定性的或非线性的,那么在没有语法大小呈指数级膨胀的情况下,无法减少其参数数量。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号