Michel Nguyen-The: Distribution of the Size of Simplified or Reduced Trees

Previous works by Casas, Fernández-Camacho and Steyaert have determined the mean and variance of the size of simplified or reduced trees of $m$-ary trees. Using the implicit function and the Quasi Powers theorems, we show that the limit distribution of that size is Gaussian.

Bibliography

CFCS90

Rafael Casas, María-Inés Fernández-Camacho, and Jean-Marc Steyaert.
Algebraic simplification in computer algebra: an analysis of bottom-up algorithms.
Theoret. Comput. Sci., 74(3):273-298, 1990.

Back to the Index