On the complexity of computing Strahler numbers

Markus Lohrey; Moses Ganardi

REVIEW 1 major objections 4 minor 12 references

On the complexity of computing Strahler numbers

T0 review · 1 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that deciding whether a binary tree's Strahler number reaches a given threshold is uNC^1-complete for term-encoded trees, with L-, P-, NL-, NP-, and PSPACE-complete variants for other representations.

desk verdict Exact complexity classifications for Strahler numbers, with a sound uNC1-completeness proof; send to peer review. read the letter →

arxiv 2512.19060 v2 pith:ITQJ7ZH3 submitted 2025-12-22 cs.CC cs.FL

Moses Ganardi , Markus Lohrey This is my paper · ORCID

classification cs.CCcs.FL MSC 68Q1568Q17

keywords StrahlernumberHorton-StrahlercircuitcomplexityuniformNC^1treestraight-lineprogramsregisterallocationcontext-freegrammarsPSPACE-completeness

topics P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The Strahler number of a binary tree measures branching complexity and equals the minimum number of registers needed to evaluate the arithmetic expression the tree represents. This paper pinpoints the exact parallel complexity of deciding whether a tree has Strahler number at least k. For term-encoded binary trees the problem is complete for uniform NC^1, the class of problems solvable by logarithmic-depth, polynomial-size circuits with bounded fan-in. For pointer-encoded trees it is logspace-complete; for DAG- or TSLP-compressed representations it is P-complete. The paper also classifies grammar-based variants: asking whether a context-free grammar has a derivation tree with Strahler number at least k is P-complete, NP-complete for fixed k≥2 when the derivation tree must be acyclic, and PSPACE-complete for acyclic derivation trees when k is part of the input.

What carries the argument

The Strahler algebra S=(N,s,0) with binary operation s(x,y)=x+1 if x=y else max(x,y) is the central object. The key structural insight is that every binary context (a tree with one placeholder leaf) computes a unary function of the form [ℓ,h](x), and these interval-shaped functions are closed under composition with an explicit four-case rule (Lemma 3.2). This characterization, combined with a known uTC^0-computable tree-balancing theorem that converts a term-encoded tree into a logarithmic-depth tree straight-line program, allows the construction of a bounded-fan-in logarithmic-depth Boolean circuit for st(t)≥k, giving membership in uNC^1. For hardness, the simulated Boolean operations f∧ an

What would settle it

Implement the reduction from Boolean formula evaluation: for balanced Boolean formulas of depth d, build the described term-encoded tree and compute its Strahler number; it should be exactly 2d+1 for true formulas and 2d for false formulas, and any deviation would falsify the uNC^1-hardness direction. Separately, brute-force the composition rule for [ℓ,h] functions over a large range of ℓ,h,m,i; a single counterexample would invalidate Lemma 3.2 and hence the circuit construction.

Watch

Extended reading notes

Core claim

The paper establishes exact complexity classifications for computing Strahler numbers. The central claim is that the decision problem St≥^term — given a binary tree as a term and a threshold k, is the Strahler number at least k? — is complete for uniform NC^1. The upper bound works by first balancing the input tree into a tree straight-line program of logarithmic depth using a known uTC^0-computable construction, then showing that every context in the Strahler algebra induces a unary function of the form [ℓ,h](x)=h if x<ℓ, h+1 if ℓ≤x≤h, and x if x>h; these functions compose according to a four-case rule, which lets the proof wire a bounded-fan-in circuit of logarithmic depth for each compari

Load-bearing premise

The uNC^1 upper bound depends on importing a theorem that every binary tree of size n can be transformed in uniform TC^0 into a tree straight-line program of logarithmic depth and linear size; if that balancing theorem is wrong or not uTC^0-computable in the required uniformity, the upper bound collapses.

Editorial extensions

If this is right

The Strahler-number decision problem for term-encoded trees is in uniform NC^1, hence in deterministic logspace, improving on previous polylogarithmic-time and logarithmic-space-with-small-factor bounds.
For pointer-encoded trees the problem is L-complete, so it is logspace-equivalent to graph accessibility in line graphs; term-encoded trees are genuinely harder in the circuit sense unless L = uNC^1.
For DAG- and TSLP-compressed trees the problem is P-complete, matching the hardness of the monotone circuit value problem; with a fixed threshold k, DAG-represented trees fall in UL∩coUL and TSLP-represented trees are NL-complete.
Deciding whether a CNF grammar has some derivation tree with Strahler number at least k is P-complete; with the acyclicity restriction, the problem is NP-complete for every fixed k≥2 and PSPACE-complete when k is part of the input.
An optimal register-allocation straight-line code for an arithmetic expression given as a term can be computed in uNC^1, since it suffices to compute the Strahler number of every subexpression.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the uNC^1-completeness holds, Strahler-number evaluation is a natural tree-evaluation problem that is not logspace-computable in general unless L=uNC^1, contrasting with arithmetic expression evaluation, which is in L; the difference likely comes from the equality-triggering nonlinearity of the operation s.
The interval-function characterization suggests a reusable recipe: for any algebra whose contexts admit a compact parametric description closed under composition, tree balancing plus gate wiring yields a uNC^1 upper bound; this may transfer to other tree parameters with similar interval behavior.
The PSPACE-completeness of acyclic derivation-tree existence with k as input is a strong lower bound: it implies that imposing the acyclicity restriction on grammar derivation trees does not simplify the Strahler question, and that the constructed grammar effectively encodes quantified Boolean formulas.
A testable boundary question left open by the paper is whether St≥3^term lies in uAC^0; resolving this would refine the constant-depth threshold for Strahler-number checking and could shed light on the power of TC^0 for tree-embedding problems.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Bottom line: this paper settles something that was genuinely open, and the main proof is sound. I think it should go to peer review and likely be accepted after minor revisions.

What's new: the exact uNC1-completeness of St_term^≥. The upper bound is the meat: it balances the input tree into a TSLP via a published theorem, then shows that every context in the Strahler algebra computes a simple [l,h] function. Lemma 3.2's composition law is verified in all four cases and is elegant. The lower bound via Buss's formula problem is clean. The rest — L-completeness for pointer representation, P-completeness for DAG/TSLP, and the grammar problems (P, NP, PSPACE) — rounds out the picture. These are natural questions and the answers are what you'd expect, but they're not in the literature, so it's a solid package.

Soft spots: the upper bound depends on Theorem 2.4, a balancing result from the authors' own earlier paper. That's fine — it's peer-reviewed and the dependency is explicit. A referee should verify the uniformity claims around the ec-representation of the circuit, but nothing looks broken. Some auxiliary reductions are terse: the uAC0-computable function in Theorem 3.4 and the grammar constructions in Theorem 4.1 rely on figures and 'straightforward' steps. I'd like a bit more detail there, but I don't see a gap. The open k=3 boundary for uAC0 is stated honestly.

Citation pattern looks appropriate; the authors cite the balancing theorem and Buss properly. No sign of circularity.

This is for a specialist audience — circuit complexity and compressed tree representations. I'd bring it to a working group if anyone cares about tree evaluation. Yes, it deserves a serious referee. I'd recommend accept with minor revisions.

Referee Report

1 major / 4 minor

Summary. The paper studies the computational complexity of deciding whether the Strahler number of a binary tree is at least a given threshold k, for several input representations. The main result is that for trees given in term representation, the problem St≥term is uNC1-complete. For pointer representation the problem is L-complete, and for DAG/TSLP representations it is P-complete. The paper also considers derivation trees of CNF grammars: deciding whether some derivation tree has Strahler number at least k is P-complete, while restricting to acyclic derivation trees gives NP-completeness for fixed k≥2 and PSPACE-completeness when k is part of the input. The proofs rely on a published tree-balancing theorem (Theorem 2.4), a new characterization of unary linear term functions in the Strahler algebra as interval functions [ℓ,h] (Lemma 3.2), and reductions from Boolean formula evaluation, graph accessibility, Majority, X3HS, and QBF.

Significance. If the results hold, they give a precise circuit-complexity classification of a natural tree parameter: computing the Strahler number of a term-encoded tree is exactly as hard as evaluating Boolean formulas in uNC1, an interesting example of tree evaluation over an infinite algebra. The interval-function composition lemma for the Strahler algebra is elegant and is likely to be useful in further work on grammar-based tree compression and register allocation. The paper also provides new complexity bounds for compressed representations and for derivation-tree problems that are relevant to recent work on group-DFA intersection and one-dimensional pushdown VASS. The main uNC1 upper bound is proved in detail, and the lower-bound reductions are mostly standard. If the P-hardness gap identified below is repaired, the paper would be a solid contribution to the field.

major comments (1)

[Theorem 3.8(i), proof] The lower bound for St≥dag is asserted in one sentence: 'one can reuse the reduction from the Boolean formula value problem in the proof of Theorem 3.1 in order to reduce the P-complete monotone Boolean circuit value problem to St≥dag.' This does not constitute a proof. In the Theorem 3.1 reduction, the threshold 2d±1 is derived from the depth of a balanced Boolean formula. For a general monotone circuit, the natural DAG encoding with the f∧/f∨ gadgets does not produce a value that separates true and false outputs by a single threshold. For example, for the monotone circuit C(x,y,z)=x∧(y∨z), the encoding yields value 4 both for input (0,1,1), where C evaluates to false, and for input (1,1,0), where C evaluates to true. Thus no k separates the two cases. A detailed reduction is needed; as written, the P-hardness of St≥dag and hence of St≥tslp is not established.

minor comments (4)

[Theorem 3.4, Claim 3.6] The proof of Claim 3.6 is informal and depends heavily on Figure 2 and phrases like 'holes', 'spine nodes', and 'the crucial observation'. Since this claim is load-bearing for the uTC0-completeness of St≥4_term, please provide a formal inductive proof or at least a much more precise description of the tree construction and the cases |w|0≥n versus |w|0<n.
[Theorem 4.1(ii)] In the grammar construction, the notation '[[O_a[I_b I_c]]]' appears to denote a nonterminal whose unique production is unary (X→Y), which is not allowed in the CNF definition. Please clarify the intended binary decomposition. Also, in the sentence 'we must have x_m∈S, y_m∉S, and z_m∉S for every j', the indices should be x_j, y_j, z_j.
[Theorem 3.7] The L-hardness reduction from line graph accessibility is described in a single paragraph with no figure. A more formal description of the constructed tree and a proof of the equivalence st(t)=3 iff (u,v)∈E* would improve readability and verifiability.
[Section 3, initial space-bound sketch] The 'gentle introduction' giving an O(log n log log n) space algorithm is sketchy and is not used later, since the uNC1 upper bound subsumes it. Consider shortening or removing it to avoid distracting the reader with an incomplete proof.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation chain is self-contained, and the cited balancing theorem is independent prior work.

full rationale

The paper's central upper bound (Theorem 3.1) rests on Theorem 2.4, imported from the same authors' earlier paper [29]. This is a load-bearing dependency, but it is not circular: the cited theorem concerns uTC0-computable construction of an O(log n)-depth TSLP for any binary tree, and its statement does not mention Strahler numbers, interval functions, or the target result. The composition lemma for [l,h] functions (Lemma 3.2) is proved directly from Eq. (2), and the rules (i)-(v) for constructing the bounded fan-in circuit B_{t,k} are derived from that lemma and the TSLP semantics. The lower bound reduces from Buss's uNC1-complete Boolean formula value problem (Theorem 2.1), an external benchmark, and the f_∧/f_∨ encodings are explicit algebra simulations, not renamed Strahler values. The fixed-k uTC0/L/NL/P/PSPACE results are each backed by explicit constructions or standard reductions. No fitted parameter is relabeled as a prediction, and no claimed result is equivalent by definition to an input assumption. The manuscript even flags its own open dependency in Section 5 for the unranked-tree extension, showing awareness of where the balancing result would need to be reproven. Accordingly, no concrete circular step can be exhibited, and the appropriate score is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper is a pure complexity-theory contribution; it introduces no fitted parameters or postulated entities. It relies on standard background theorems (Buss's NC1-completeness, L- and P-completeness of known problems, NL closure, alternating polynomial time = PSPACE), plus the authors' own published balancing theorem which is independent of the target results.

assumptions (7)

standard math Buss's theorem: Boolean formula value problem is uNC^1-complete
Used as the basis for the uNC1 lower bound in Theorem 3.1.
domain assumption Tree balancing theorem: every binary tree of size n can be transformed in uTC0 into a TSLP of depth O(log n) and size O(n)
Key for the uNC1 upper bound in Theorem 3.1; stated as Theorem 2.4 and not proven in this paper.
standard math Line graph accessibility problem is L-complete
Used for L-hardness of St^{pointer}_{≥3} in Theorem 3.7.
standard math Monotone circuit value problem is P-complete
Used for P-hardness in Theorem 3.8(i).
standard math Immerman–Szelepcsényi theorem: NL is closed under complement
Used to conclude NL membership from alternating logspace with k alternations in Theorem 3.8(iii).
standard math Positive 1-in-3-SAT is NP-complete
Used for NP-hardness of acCNF^{≥2} in Theorem 4.1(ii).
standard math Alternating polynomial time equals PSPACE
Used for the PSPACE upper bound in Theorem 4.1(iii).

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the complexity of computing Strahler numbers." pith.science (2026). https://pith.science/paper/ITQJ7ZH3

@misc{pith2026251219060,
  author       = {Pith},
  title        = {Pith review of: On the complexity of computing Strahler numbers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ITQJ7ZH3}},
  note         = {Machine review of arXiv:2512.19060}
}

abstract

It is shown that the problem of computing the Strahler number of a binary tree given as a term is complete for the circuit complexity class uniform $\mathsf{NC}^1$. For several variants, where the binary tree is given by a pointer structure or in a succinct form by a directed acyclic graph or a tree straight-line program, the complexity of computing the Strahler number is determined as well. We show that the problem of deciding whether a given context-free grammar in Chomsky normal form produces a derivation tree with a Strahler number of at least $k$ is $\mathsf{P}$-complete. If the derivation tree is restricted to be acyclic, the problem becomes $\mathsf{PSPACE}$-complete.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 5 canonical work pages

[9]

37 Robert E. Horton. Erosional development of streams and their drainage basins: hydro-physical approach to quantitative morphology.Geological Society of America Bulletin, 56(3):275–370, 1945.doi:10.1130/0016-7606(1945)56[275:EDOSAT]2.0.CO;2. 38 Neil Immerman. Nondeterministic space is closed under complementation.SIAM Journal on Computing, 17(5):935–938,...

work page doi:10.1130/0016-7606(1945)56 1945
[12]

58 Heribert Vollmer.Introduction to Circuit Complexity - A Uniform Approach

Available online athttp://www.xavierviennot.org. 58 Heribert Vollmer.Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoret- ical Computer Science. An EATCS Series. Springer, 1999.doi:10.1007/978-3-662-03927-4. 59 R. Ryan Williams. Simulating time with square-root space. In Michal Koucký and Nikhil Bansal, editors,Proceedings of the 57t...

arXiv 1999
[66]

On programming of arithmetic operations.Communications of the ACM, 1(8):3–6, 1958.doi:10.1145/368892.368907

23 Andrey Petrovich Ershov. On programming of arithmetic operations.Communications of the ACM, 1(8):3–6, 1958.doi:10.1145/368892.368907. 24 Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Newtonian program analysis.Journal of the ACM, 57(6), 2010.doi:10.1145/1857914.1857917. 25 Javier Esparza, Michael Luttenberger, and Maximilian Schlund. A brief...

arXiv 1958
[1035]

Computing algebraic formulas using a constant number of registers.SIAM Journal on Computing, 21(1):54–58, 1992.doi:10.1137/0221006

6 Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers.SIAM Journal on Computing, 21(1):54–58, 1992.doi:10.1137/0221006. 7 Clotilde Bizière and Wojciech Czerwinski. Reachability in one-dimensional pushdown vector addition systems is decidable. InProceedings of the 57th Annual ACM Symposium on Theory of Comput...

arXiv 1992
[1971]

Strahler

54 Arthur N. Strahler. Hypsometric (area-altitude) analysis of erosional topology.Geological Society of America Bulletin, 63(11):1117–1142, 1952.doi:10.1130/0016-7606(1952)63[1117: HAAOET]2.0.CO;2. 55 Ivan Hal Sudborough. On the tape complexity of deterministic context-free languages.Journal of the ACM, 25(3):405–414, 1978.doi:10.1145/322077.322083. 56 Jo...

arXiv 1952
[1979]

28 Philippe Flajolet, Paolo Sipala, and Jean-Marc Steyaert

doi:10.1016/0304-3975(79)90009-4. 28 Philippe Flajolet, Paolo Sipala, and Jean-Marc Steyaert. Analytic variations on the common subexpression problem. InProceedings of the 17th International Colloquium on Automata, Languages and Programming, ICALP 1990, volume 443 ofLecture Notes in Computer Science, pages 220–234. Springer, 1990.doi:10.1007/BFB0032034. 2...

work page doi:10.1016/0304-3975(79)90009-4 1990
[1990]

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter

doi:10.1007/ 3-540-53487-3\_48. 42 Andreas Krebs, Nutan Limaye, and Michael Ludwig. A unified method for placing problems in polylogarithmic depth. InProceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, volume 93 of LIPIcs, pages 36:36–36:15. Schloss Dagstuhl - Leibniz-Zentrum...

work page Pith review arXiv doi:10.48550/arxiv.2505.13749 2017
[1996]

19 Peter J

doi:10.1051/ ita/1996300504431. 19 Peter J. Downey, Ravi Sethi, and Robert Endre Tarjan. Variations on the common subexpres- sion problem.Journal of the ACM, 27(4):758–771, 1980.doi:10.1145/322217.322228. 20 Andrzej Ehrenfeucht, Grzegorz Rozenberg, and Dirk Vermeir. On ETOL systems with finite tree-rank.SIAM Journal on Computing, 10(1):40–58, 1981.doi:10....

arXiv 1980

Show all 12 references

[2004]

2 Sanjeev Arora and Boaz Barak.Computational Complexity - A Modern Approach

doi:10.1140/epjb/e2004-00130-1. 2 Sanjeev Arora and Boaz Barak.Computational Complexity - A Modern Approach. Cambridge University Press, 2009.doi:10.1017/CBO9780511804090. 3 Mohamed Faouzi Atig and Pierre Ganty. Approximating Petri net reachability along context- free traces. ...

2009 doi
[2010]

22 Michael Elberfeld, Andreas Jakoby, and Till Tantau

doi: 10.1109/FOCS.2010.21. 22 Michael Elberfeld, Andreas Jakoby, and Till Tantau. Algorithmic meta theorems for circuit classes of constant and logarithmic depth. InProceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, volume 1...

2010 doi
[2011]

FSTTCS.2011.152

doi:10.4230/LIPICS. FSTTCS.2011.152. 4 David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity withinNC1. Journal of Computer and System Sciences, 41:274–306, 1990.doi:10.1016/0022-0000(90) 90022-D. 5 Martin Beaudry and Pierre McKenzie. Circuits, matrices, ...

2011 doi
[2020]

33 Seymour Ginsburg and Edwin H

doi:10.1007/S00224-019-09942-Y. 33 Seymour Ginsburg and Edwin H. Spanier. Derivation-bounded languages.Journal of Computer and System Sciences, 2(3):228–250, 1968.doi:10.1016/S0022-0000(68)80009-1. 34 Jozef Gruska. A few remarks on the index of context-free grammars and langua...

1968 doi

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [9]

37 Robert E. Horton. Erosional development of streams and their drainage basins: hydro-physical approach to quantitative morphology.Geological Society of America Bulletin, 56(3):275–370, 1945.doi:10.1130/0016-7606(1945)56[275:EDOSAT]2.0.CO;2. 38 Neil Immerman. Nondeterministic space is closed under complementation.SIAM Journal on Computing, 17(5):935–938,...

work page doi:10.1130/0016-7606(1945)56 1945

[2] [12]

58 Heribert Vollmer.Introduction to Circuit Complexity - A Uniform Approach

Available online athttp://www.xavierviennot.org. 58 Heribert Vollmer.Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoret- ical Computer Science. An EATCS Series. Springer, 1999.doi:10.1007/978-3-662-03927-4. 59 R. Ryan Williams. Simulating time with square-root space. In Michal Koucký and Nikhil Bansal, editors,Proceedings of the 57t...

arXiv 1999

[3] [66]

On programming of arithmetic operations.Communications of the ACM, 1(8):3–6, 1958.doi:10.1145/368892.368907

23 Andrey Petrovich Ershov. On programming of arithmetic operations.Communications of the ACM, 1(8):3–6, 1958.doi:10.1145/368892.368907. 24 Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Newtonian program analysis.Journal of the ACM, 57(6), 2010.doi:10.1145/1857914.1857917. 25 Javier Esparza, Michael Luttenberger, and Maximilian Schlund. A brief...

arXiv 1958

[4] [1035]

Computing algebraic formulas using a constant number of registers.SIAM Journal on Computing, 21(1):54–58, 1992.doi:10.1137/0221006

6 Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers.SIAM Journal on Computing, 21(1):54–58, 1992.doi:10.1137/0221006. 7 Clotilde Bizière and Wojciech Czerwinski. Reachability in one-dimensional pushdown vector addition systems is decidable. InProceedings of the 57th Annual ACM Symposium on Theory of Comput...

arXiv 1992

[5] [1971]

Strahler

54 Arthur N. Strahler. Hypsometric (area-altitude) analysis of erosional topology.Geological Society of America Bulletin, 63(11):1117–1142, 1952.doi:10.1130/0016-7606(1952)63[1117: HAAOET]2.0.CO;2. 55 Ivan Hal Sudborough. On the tape complexity of deterministic context-free languages.Journal of the ACM, 25(3):405–414, 1978.doi:10.1145/322077.322083. 56 Jo...

arXiv 1952

[6] [1979]

28 Philippe Flajolet, Paolo Sipala, and Jean-Marc Steyaert

doi:10.1016/0304-3975(79)90009-4. 28 Philippe Flajolet, Paolo Sipala, and Jean-Marc Steyaert. Analytic variations on the common subexpression problem. InProceedings of the 17th International Colloquium on Automata, Languages and Programming, ICALP 1990, volume 443 ofLecture Notes in Computer Science, pages 220–234. Springer, 1990.doi:10.1007/BFB0032034. 2...

work page doi:10.1016/0304-3975(79)90009-4 1990

[7] [1990]

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter

doi:10.1007/ 3-540-53487-3\_48. 42 Andreas Krebs, Nutan Limaye, and Michael Ludwig. A unified method for placing problems in polylogarithmic depth. InProceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, volume 93 of LIPIcs, pages 36:36–36:15. Schloss Dagstuhl - Leibniz-Zentrum...

work page Pith review arXiv doi:10.48550/arxiv.2505.13749 2017

[8] [1996]

19 Peter J

doi:10.1051/ ita/1996300504431. 19 Peter J. Downey, Ravi Sethi, and Robert Endre Tarjan. Variations on the common subexpres- sion problem.Journal of the ACM, 27(4):758–771, 1980.doi:10.1145/322217.322228. 20 Andrzej Ehrenfeucht, Grzegorz Rozenberg, and Dirk Vermeir. On ETOL systems with finite tree-rank.SIAM Journal on Computing, 10(1):40–58, 1981.doi:10....

arXiv 1980