[Zurück]

M. Wallner, A. Price:
"Stretched exponentials for compacted binary trees and a class of minimal automata";
Vortrag: Séminaire d´algorithmique, Paris; 21.01.2020.

A compacted binary tree is a directed acyclic graph encoding a binary tree in which common subtrees are factored and shared, such that they are represented only once. We show that the number of compacted binary trees of size n is asymptotically given by Theta(n! 4^n e^(3 a_1 n^(1/3)) n^(3/4) ), where a_1 is the largest root of the Airy function and approximately equal to 2.338. Our method involves a new two parameter recurrence which yields an algorithm of quadratic arithmetic complexity for computing the number of compact trees of a given size. We use empirical methods to estimate the values of all terms defined by the recurrence, then we prove by induction that these estimates are sufficiently accurate for large n to determine the asymptotic form of the number of compacted trees. Our results also lead to new bounds on the number of minimal finite automata recognizing a finite language on a binary alphabet showing the appearance of a stretched exponential. This is joint work with Andrew Elvey Price and Wenjie Fang.