A Universal Tree Balancing Theorem
A Universal Tree Balancing Theorem
复制标题
通用树平衡定理
DOI：
10.1145/3278158
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Markus Lohrey
中科院分区：
文献类型：
--
作者：
Moses Ganardi;Markus Lohrey
我们提出了一个一般的框架，平衡表达式（条款）的形式，所谓的树直线程序。后者可以被看作是由上下文（带洞的项）和操作扩展的自由项代数上的电路，这些操作将项/上下文插入上下文。在文献[16]中，我们证明了对于给定的对数空间中的sizen项，可以计算出深度为O（logn），大小为O（n/ logn）的树型直线规划。在本文中，它表明，转换可以在DLOGTIME均匀的TC 0。这允许将任意代数A上的项求值问题简化为导出的二排序代数F（A）上的项求值问题。提出了三种应用：（i）给出了Krebs等人[25]关于表达式求值问题的一个新结果的另一种证明;（ii）证明了任意（可能是非交换的）半环的表达式可以在DLOGTIME-均匀TC 0中变换为对数深度和大小为O（n/ logn）的等效电路;（iii）给出了正则表达式的相应结果。
We present a general framework for balancing expressions (terms) in the form of so-called tree straight-line programs. The latter can be seen as circuits over the free term algebra extended by contexts (terms with a hole) and the operations, which insert terms/contexts into contexts. In Ref. [16], it was shown that one can compute for a given term of sizenin logspace a tree straight-line program of depthO(logn) and sizeO(n/ logn). In the present article, it is shown that the conversion can be done in DLOGTIME-uniform TC0. This allows reducing the term evaluation problem over an arbitrary algebra A to the term evaluation problem over a derived two-sorted algebraF(A). Three applications are presented: (i) an alternative proof for a recent result by Krebs et al. [25] on the expression evaluation problem is given; (ii) it is shown that expressions for an arbitrary (possibly non-commutative) semiring can be transformed in DLOGTIME-uniform TC0into equivalent circuits of logarithmic depth and sizeO(n/ logn); and, (iii) a corresponding result for regular expressions is shown.
登录
查看更多内容
影响因子：
0.5
作者：
Adrià Gascón;Markus Lohrey;S. Maneth;C. Reh;K. Sieber
通讯作者：
Adrià Gascón;Markus Lohrey;S. Maneth;C. Reh;K. Sieber
DOI：
10.1016/s0304-3975(97)00227-2
发表时间：
1996
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Eric Allender;Jia Jiao;M. Mahajan;V. Vinay
通讯作者：
V. Vinay
影响因子：
3.7
作者：
Lohrey, Markus;Maneth, Sebastian;Mennicke, Roy
通讯作者：
Mennicke, Roy
布尔公式值问题在ALOGTIME中
DOI：
10.1145/28395.28409
发表时间：
1987
期刊：
Proceedings of the nineteenth annual ACM symposium on Theory of computing
影响因子：
--
作者：
S. Buss
通讯作者：
S. Buss
DOI：
10.1137/0221046
发表时间：
1992
期刊：
SIAM J. Comput.
影响因子：
--
作者：
S. Buss;S. Cook;A. Gupta;V. Ramachandran
通讯作者：
V. Ramachandran