research-article

A Universal Tree Balancing Theorem

Authors:

Markus LohreyAuthors Info & Claims

ACM Transactions on Computation Theory (TOCT), Volume 11, Issue 1

Article No.: 1, Pages 1 - 25

https://doi.org/10.1145/3278158

Published: 22 October 2018 Publication History

Abstract

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 n in logspace a tree straight-line program of depth O(log n) and size O(n/ log n). In the present article, it is shown that the conversion can be done in DLOGTIME-uniform TC⁰. This allows reducing the term evaluation problem over an arbitrary algebra A to the term evaluation problem over a derived two-sorted algebra F (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 TC⁰ into equivalent circuits of logarithmic depth and size O(n/ log n); and, (iii) a corresponding result for regular expressions is shown.

References

[1]

Karl R. Abrahamson, Norm Dadoun, David G. Kirkpatrick, and Teresa M. Przytycka. 1989. A simple parallel tree contraction algorithm. Journal of Algorithms 10, 2, 287--302

Digital Library

[2]

Eric Allender, Jia Jiao, Meena Mahajan, and V. Vinay. 1998. Non-commutative arithmetic circuits: Depth reduction and size lower bounds. Theoretical Computer Science 209, 1--2, 47--86.

Digital Library

[3]

David A. M. Barrington, Neil Immerman, and Howard Straubing. 1990. On uniformity within . Journal of Computer and System Sciences 41, 3, 274--306.

Digital Library

[4]

Philip Bille, Inge Li Gørtz, Gad M. Landau, and Oren Weimann. 2015. Tree compression with top trees. Information and Computation 243, 166--177.

Digital Library

[5]

Maria Luisa Bonet and Samuel R. Buss. 1994. Size-depth tradeoffs for Boolean fomulae. Information Processing Letters 49, 3, 151--155.

Digital Library

[6]

Richard P. Brent. 1974. The parallel evaluation of general arithmetic expressions. Journal of the ACM 21, 2, 201--206.

Digital Library

[7]

Nader H. Bshouty, Richard Cleve, and Wayne Eberly. 1995. Size-depth tradeoffs for algebraic formulas. SIAM Journal on Computing 24, 4, 682--705.

Digital Library

[8]

S. Buss, S. Cook, A. Gupta, and V. Ramachandran. 1992. An optimal parallel algorithm for formula evaluation. SIAM Journal on Computing 21, 4, 755--780.

Digital Library

[9]

Samuel R. Buss. 1987. The Boolean formula value problem is in ALOGTIME. In Proceedings of the 19th Annual Symposium on Theory of Computing (STOC’87). ACM Press, 123--131.

Digital Library

[10]

Samuel R. Buss. 1993. Algorithms for Boolean formula evaluation and for tree-contraction. Proof Theory, Complexity, and Arithmetic 95--115.

[11]

M. Charikar, E. Lehman, A. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, and A. Shelat. 2005. The smallest grammar problem. IEEE Transactions on Information Theory 51, 7, 2554--2576.

Digital Library

[12]

Stephen A. Cook and Pierre McKenzie. 1987. Problems complete for deterministic logarithmic space. Journal of Algorithms 8, 3, 385--394.

Digital Library

[13]

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.

Digital Library

[14]

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’18), volume 105 of LIPIcs. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 16:1--16:8.

[15]

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—Leibniz-Zentrum für Informatik, 66--77.

[16]

Moses Ganardi, Danny Hucke, Artur Jez, Markus Lohrey, and Eric Noeth. 2017. Constructing small tree grammars and small circuits for formulas. Journal of Computer and System Sciences 86, 136--158.

Digital Library

[17]

Moses Ganardi, Danny Hucke, Daniel König, and Markus Lohrey. 2018. Circuits and expressions over finite semirings. Accepted for publication in ACM Transactions on Computation Theory.

Digital Library

[18]

Adrià Gascón, Markus Lohrey, Sebastian Maneth, Carl Philipp Reh, and Kurt Sieber. 2018. Grammar-based compression of unranked trees. In Proceedings of 13th International Computer Science Symposium in Russia (CSR’18), volume 10846 of Lecture Notes in Computer Science. Springer, 118--131.

Digital Library

[19]

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.

[20]

Hermann Gruber and Markus Holzer. 2008. Finite automata, digraph connectivity, and regular expression size. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Part II, volume 5126 of Lecture Notes in Computer Science. Springer, 39--50.

Digital Library

[21]

William Hesse, Eric Allender, and David A. Mix Barrington. 2002. Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences 65, 4, 695--716.

Digital Library

[22]

Danny Hucke and Markus Lohrey. 2017. Universal tree source coding using grammar-based compression. In Proceedings of the IEEE International Symposium on Information Theory, ISIT 2017. IEEE, 1753--1757.

[23]

Neil Immerman. 1999. Descriptive Complexity. Graduate texts in computer science. Springer.

[24]

Artur Jez and Markus Lohrey. 2016. Approximation of smallest linear tree grammar. Information and Computation 251, 215--251.

Digital Library

[25]

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—Leibniz-Zentrum für Informatik, 36:36--36:15.

[26]

Markus Lohrey. 2001. On the parallel complexity of tree automata. In Proceedings of the 12th International Conference on Rewrite Techniques and Applications, RTA 2001, volume 2051 of Lecture Notes in Computer Science. Springer, 201--215.

Digital Library

[27]

Markus Lohrey. 2015. Grammar-based tree compression. In Proceedings of the 19th International Conference on Developments in Language Theory, DLT 2015, volume 9168 of Lecture Notes in Computer Science. Springer, 46--57.

[28]

Markus Lohrey, Sebastian Maneth, and Roy Mennicke. 2013. XML tree structure compression using RePair. Information Systems 38, 8, 1150--1167.

Digital Library

[29]

Gary L. Miller and Shang-Hua Teng. 1987. Dynamic Parallel Complexity of Computational Circuits. In Proceedings of the 19th Annual Symposium on Theory of Computing, STOC 1987. ACM Press, 254--263.

Digital Library

[30]

Gary L. Miller and Shang-Hua Teng. 1997. Tree-based parallel algorithm design. Algorithmica 19, 4, 369--389.

[31]

Mike Paterson and Leslie G. Valiant. 1976. Circuit size is nonlinear in depth. Theoretical Computer Science 2, 3, 397--400.

[32]

Walter L. Ruzzo. 1981. On uniform circuit complexity. Journal of Computer and System Sciences 22, 3, 365--383.

[33]

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.

[34]

Leslie G. Valiant, Sven Skyum, S. Berkowitz, and Charles Rackoff. 1983. Fast parallel computation of polynomials using few processors. SIAM Journal on Computing 12, 4, 641--644.

[35]

Heribert Vollmer. 1999. Introduction to Circuit Complexity. Springer.

Digital Library

[36]

Wolfgang Wechler. 1992. Universal Algebra for Computer Scientists, volume 25 of EATCS Monographs on Theoretical Computer Science. Springer.

Cited By

Ganardi MJeż ALohrey M(2021)Balancing Straight-line ProgramsJournal of the ACM10.1145/345738968:4(1-40)Online publication date: 30-Jun-2021
https://dl.acm.org/doi/10.1145/3457389
Hucke DLohrey MBenkner L(2021)Entropy Bounds for Grammar-Based Tree CompressorsIEEE Transactions on Information Theory10.1109/TIT.2021.311267667:11(7596-7615)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1109/TIT.2021.3112676
Hucke DLohrey MBenkner L(2019)Entropy Bounds for Grammar-Based Tree Compressors2019 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2019.8849372(1687-1691)Online publication date: Jul-2019
https://doi.org/10.1109/ISIT.2019.8849372
Show More Cited By

Index Terms

A Universal Tree Balancing Theorem
1. Theory of computation
  1. Computational complexity and cryptography
    1. Circuit complexity

Recommendations

Arithmetic circuits: The chasm at depth four gets wider

In their paper on the ''chasm at depth four'', Agrawal and Vinay have shown that polynomials in m variables of degree O(m) which admit arithmetic circuits of size 2^o^(^m^) also admit arithmetic circuits of depth four and size 2^o^(^m^). This theorem ...
Finding a k-Tree Core and a k-Tree Center of a Tree Network in Parallel

A k-tree core of a tree network is a subtree with exactly k leaves that minimizes the total distance from vertices to the subtree. A k-tree center of a tree network is a subtree with exactly k leaves that minimizes the distance from the farthest vertex ...
Bottom-Up tree evaluation in tree-based genetic programming
ICSI'10: Proceedings of the First international conference on Advances in Swarm Intelligence - Volume Part I

In tree-based genetic programming (GP) performance optimization, the primary optimization target is the process of fitness evaluation This is because fitness evaluation takes most of execution time in GP Standard fitness evaluation uses the top-down ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computation Theory

ACM Transactions on Computation Theory Volume 11, Issue 1

March 2019

145 pages

ISSN:1942-3454

EISSN:1942-3462

DOI:10.1145/3287761

Editor:
Venkatesan Guruswami
Carnegie Mellon University, USA

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2018

Accepted: 01 August 2018

Revised: 01 May 2018

Received: 01 October 2017

Published in TOCT Volume 11, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
154
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ganardi MJeż ALohrey M(2021)Balancing Straight-line ProgramsJournal of the ACM10.1145/345738968:4(1-40)Online publication date: 30-Jun-2021
https://dl.acm.org/doi/10.1145/3457389
Hucke DLohrey MBenkner L(2021)Entropy Bounds for Grammar-Based Tree CompressorsIEEE Transactions on Information Theory10.1109/TIT.2021.311267667:11(7596-7615)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1109/TIT.2021.3112676
Hucke DLohrey MBenkner L(2019)Entropy Bounds for Grammar-Based Tree Compressors2019 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2019.8849372(1687-1691)Online publication date: Jul-2019
https://doi.org/10.1109/ISIT.2019.8849372
Ganardi MJez ALohrey M(2019)Balancing Straight-Line Programs2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2019.00073(1169-1183)Online publication date: Nov-2019
https://doi.org/10.1109/FOCS.2019.00073

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents