A universal tree balancing theorem

DOI10.1145/3278158MaRDI QIDQ5205802zbMATHOpenAlexWikidataFDO

Authors Moses Ganardi, Markus Lohrey

Publication date 16 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.08705

zbMATH Keywords

tree evaluationdepth reductiontree contraction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Semirings (16Y60) Applications of universal algebra in computer science (08A70)

Abstract: We present a general framework for balancing expressions (terms) in 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. It is shown that for every term one can compute in DLOGTIME-uniform TC${}^0$ a tree straight-line program of logarithmic depth and size $O(n/logn)$. This allows reducing the term evaluation problem over an arbitrary algebra $mathcalA$ to the term evaluation problem over a derived two-sorted algebra $mathcalF(mathcalA)$. Several applications are presented: (i) an alternative proof for a recent result by Krebs, Limaye and Ludwig 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 TC${}^0$ into equivalent circuits of logarithmic depth and size $O(n/logn)$, and (iii) a corresponding result for regular expressions is shown.

Recommendations

• Balancing Straight-line Programs
• A unified method for placing problems in polylogarithmic depth
• Constructing small tree grammars and small circuits for formulas
• Constructing small tree grammars and small circuits for formulas
• Pebbles and branching programs for tree evaluation

Cited in

(3)

• A unified method for placing problems in polylogarithmic depth
• Balanced trees with removals: An exercise in rewriting and proof
• Balancing Straight-line Programs

This page was built for publication: A universal tree balancing theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205802)