A universal tree balancing theorem

DOI10.1145/3278158zbMATH Open1485.68082arXiv1704.08705OpenAlexW2963653005WikidataQ129043902 ScholiaQ129043902MaRDI QIDQ5205802FDOQ5205802

Authors: Moses Ganardi, Markus Lohrey 

Publication date: 16 December 2019

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

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.

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

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

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)

Cited In (3)

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

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)