Abstract: 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 equal to

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 method also allows to enumerate minimal finite automata recognizing a finite language on a binary alphabet. This again shows the appearance of a stretched exponential. This is joint work with Andrew Elvey Price and Wenjie Fang.

Zoom-Meeting beitreten: https://zoom.us/j/95266898496?pwd=VE1SZG0reFBwTlVhNzU5ZlJieDFHUT09
Meeting-ID: 952 6689 8496
Kenncode: p291Sc