Constructing small tree grammars and small circuits for formulas

Moses Ganardi, Danny Hucke, Artur Jez +2

It is shown that every tree of size $n$ over a fixed set of $\sigma$ different ranked symbols can be decomposed (in linear time as well as in logspace) into $O\big(\frac{n}{\log_σn}\big…