moteur de recherche

Séminaire Algo - Michael Wallner
Séminaire Algo - Michael Wallner
21-Jan-2020 14:00
Age: 169 days

Michael Wallner

Stretched exponentials for compacted binary trees and a class of minimal automata

Salle de séminaire (4B125) - Bâtiment Copernic

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 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.

<- Back to: Accueil