Parameter reduction and automata evaluation for grammar-compressed trees
Parameter reduction and automata evaluation for grammar-compressed trees
复制标题
DOI：
10.1016/j.jcss.2012.03.003
复制
发表时间：
2012-09
期刊：
影响因子：
--
通讯作者：
Markus Lohrey;S. Maneth;M. Schmidt-Schauß
中科院分区：
文献类型：
--
作者：
Markus Lohrey;S. Maneth;M. Schmidt-Schauß
树可以很方便地压缩线性直线上下文无关树文法。这样的文法概括了直线上下文无关的字符串文法，其广泛用于直接在压缩结构上执行的算法的开发中（没有预先解压缩）。本文证明了任何线性直线上下文无关树文法都可以在多项式时间内变换成一元（线性）文法。一个树文法是一元的，如果每个非终结符至多使用一个上下文参数。在此基础上，给出了多项式时间算法来检验给定的（i）非确定树自动机或（ii）具有兄弟约束的非确定树自动机或（iii）非确定树行走自动机是否接受由线性直线上下文无关树文法表示的树.它还表明，如果树文法是非确定性或非线性的，那么减少它们的参数的数量不能没有一个指数爆破的语法大小。
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, polynomial time algorithms are presented for testing whether a given (i) nondeterministic tree automaton or (ii) nondeterministic tree automaton with sibling-constraints or (iii) nondeterministic tree walking automaton, accepts a tree represented by a linear straight-line context-free tree grammar. It is also shown that if tree grammars are nondeterministic or non-linear, then reducing their numbers of parameters cannot be done without an exponential blow-up in grammar size.