A Universal Tree Balancing Theorem
Moses Ganardi, Markus Lohrey · ACM Transactions on Computation Theory · 2018
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.