{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:17Z","timestamp":1750220957851,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,10,22]],"date-time":"2018-10-22T00:00:00Z","timestamp":1540166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,3,31]]},"abstract":"<jats:p>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 size<jats:italic>n<\/jats:italic>in logspace a tree straight-line program of depth<jats:italic>O<\/jats:italic>(log<jats:italic>n<\/jats:italic>) and size<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>\/ log<jats:italic>n<\/jats:italic>). In the present article, it is shown that the conversion can be done in DLOGTIME-uniform TC<jats:sup>0<\/jats:sup>. This allows reducing the term evaluation problem over an arbitrary algebra A to the term evaluation problem over a derived two-sorted algebra<jats:italic>F<\/jats:italic>(<jats:italic>A<\/jats:italic>). 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 TC<jats:sup>0<\/jats:sup>into equivalent circuits of logarithmic depth and size<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>\/ log<jats:italic>n<\/jats:italic>); and, (iii) a corresponding result for regular expressions is shown.<\/jats:p>","DOI":"10.1145\/3278158","type":"journal-article","created":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T12:16:16Z","timestamp":1540296976000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A Universal Tree Balancing Theorem"],"prefix":"10.1145","volume":"11","author":[{"given":"Moses","family":"Ganardi","sequence":"first","affiliation":[{"name":"University of Siegen, Germany"}]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[{"name":"University of Siegen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2018,10,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90017-5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00227-2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.012"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90093-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792232586"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221046"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28409"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Samuel R. Buss. 1993. Algorithms for Boolean formula evaluation and for tree-contraction. Proof Theory Complexity and Arithmetic 95--115. Samuel R. Buss. 1993. Algorithms for Boolean formula evaluation and for tree-contraction. Proof Theory Complexity and Arithmetic 95--115.","DOI":"10.1093\/oso\/9780198536901.003.0005"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90018-6"},{"volume-title":"Handbook of Theoretical Computer Science","author":"Dershowitz Nachum","key":"e_1_2_1_13_1","unstructured":"Nachum Dershowitz and Jean-Pierre Jouannaud . 1990. Rewrite systems . In Handbook of Theoretical Computer Science , Volume B: Formal Models and Semantics (B). Elsevier, 243-- 320 . Nachum Dershowitz and Jean-Pierre Jouannaud. 1990. Rewrite systems. In Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics (B). Elsevier, 243--320."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM\u201918)","volume":"105","author":"Dudek Bartlomiej","year":"2018","unstructured":"Bartlomiej Dudek and Pawel Gawrychowski . 2018 . Slowing down top trees for better worst-case compression . In Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM\u201918) , volume 105 of LIPIcs. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, 16:1--16:8. Bartlomiej Dudek and Pawel Gawrychowski. 2018. Slowing down top trees for better worst-case compression. In Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM\u201918), volume 105 of LIPIcs. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, 16:1--16:8."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science, STACS 2012","volume":"14","author":"Elberfeld Michael","year":"2012","unstructured":"Michael Elberfeld , Andreas Jakoby , and Till Tantau . 2012 . Algorithmic meta theorems for circuit classes of constant and logarithmic depth . In Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science, STACS 2012 , volume 14 of LIPIcs. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, 66--77. Michael Elberfeld, Andreas Jakoby, and Till Tantau. 2012. Algorithmic meta theorems for circuit classes of constant and logarithmic depth. In Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science, STACS 2012, volume 14 of LIPIcs. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, 66--77."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.12.007"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241375"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-90530-3_11"},{"volume-title":"Concurrent Computations: Algorithms, Architecture and Technology.","author":"Gazit Hillel","key":"e_1_2_1_19_1","unstructured":"Hillel Gazit , Gary L. Miller , and Shang-Hua Teng . 1988. Optimal tree contraction in an EREW model . In S. K. Tewksbury, B. W. Dickinson, and S. C. Schwartz (Eds.). Concurrent Computations: Algorithms, Architecture and Technology. New York , Plenum Press , 139--156. Hillel Gazit, Gary L. Miller, and Shang-Hua Teng. 1988. Optimal tree contraction in an EREW model. In S. K. Tewksbury, B. W. Dickinson, and S. C. Schwartz (Eds.). Concurrent Computations: Algorithms, Architecture and Technology. New York, Plenum Press, 139--156."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00025-9"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2017.8006830"},{"volume-title":"Graduate texts in computer science","author":"Immerman Neil","key":"e_1_2_1_23_1","unstructured":"Neil Immerman . 1999. Descriptive Complexity . Graduate texts in computer science . Springer . Neil Immerman. 1999. Descriptive Complexity. Graduate texts in computer science. Springer."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.09.007"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017","volume":"93","author":"Krebs Andreas","year":"2018","unstructured":"Andreas Krebs , Nutan Limaye , and Michael Ludwig . 2018 . A unified method for placing problems in polylogarithmic depth . In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017 , volume 93 of LIPIcs. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, 36:36--36:15. Andreas Krebs, Nutan Limaye, and Michael Ludwig. 2018. A unified method for placing problems in polylogarithmic depth. In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, volume 93 of LIPIcs. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, 36:36--36:15."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/647200.718725"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21500-6_3"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.06.006"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28423"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009179"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90090-6"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90038-6"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 4th Hawaii International Symposium on System Sciences. 525--527","author":"Spira Philip M.","year":"1971","unstructured":"Philip M. Spira . 1971 . On time-hardware complexity tradeoffs for Boolean functions . In Proceedings of the 4th Hawaii International Symposium on System Sciences. 525--527 . Philip M. Spira. 1971. On time-hardware complexity tradeoffs for Boolean functions. In Proceedings of the 4th Hawaii International Symposium on System Sciences. 525--527."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"volume-title":"Introduction to Circuit Complexity","author":"Vollmer Heribert","key":"e_1_2_1_35_1","unstructured":"Heribert Vollmer . 1999. Introduction to Circuit Complexity . Springer . Heribert Vollmer. 1999. Introduction to Circuit Complexity. Springer."},{"key":"e_1_2_1_36_1","series-title":"EATCS Monographs on Theoretical Computer Science","volume-title":"Universal Algebra for Computer Scientists","author":"Wechler Wolfgang","unstructured":"Wolfgang Wechler . 1992. Universal Algebra for Computer Scientists , volume 25 of EATCS Monographs on Theoretical Computer Science . Springer . Wolfgang Wechler. 1992. Universal Algebra for Computer Scientists, volume 25 of EATCS Monographs on Theoretical Computer Science. Springer."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3278158","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3278158","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:09Z","timestamp":1750204449000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3278158"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,22]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,31]]}},"alternative-id":["10.1145\/3278158"],"URL":"https:\/\/doi.org\/10.1145\/3278158","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2018,10,22]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}