Compacted binary trees admit a stretched exponential

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:177

Article

Price, Andrew Elvey¹  Fang, Wenjie²  Wallner, Michael^1,3 

[1] Univ Bordeaux, Lab Bordelais Rech Informat, UMR 5800, 351 Cours Liberat, F-33405 Talence, France

[2] Univ Gustave Eiffel, Lab Informat Gaspard Monge, ESIEE Paris, CNRS,UMR 8049, 5 Blvd Descartes, F-77454 Marne La Vallee, France

[3] TU Wien, Inst Discrete Math & Geometry, Wiedner Hauptstr 8-10, A-1040 Vienna, Austria

关键词: Airy function;    Asymptotics;    Bijection;    Compacted trees;    Directed acyclic graphs;    Dyck paths;    Finite languages;    Minimal automata;    Stretched exponential;   

DOI  :  10.1016/j.jcta.2020.105306

来源: Elsevier

【 摘 要 】

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 ngrows asymptotically like Theta(n!4(n)e3(a)1n(1/2) n(3/4))where a(1) approximate to -2.338 is the largest root of the Airy function. Our method involves a new two parameter recurrence which yields an algorithm of quadratic arithmetic complexity for computing the number of compacted trees up to 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. Our results also lead to new bounds on the number of minimal finite automata recognizing a finite language on a binary alphabet. As a consequence, these also exhibit a stretched exponential. (C) 2020 Elsevier Inc. All rights reserved.

【 授权许可】

Free