Compacted binary trees admit a stretched exponential

DOI10.1016/J.JCTA.2020.105306MaRDI QIDQ2005184zbMATH OpenOpenAlexWikidataFDO

Authors Andrew Elvey Price, W. Fang, Michael Wallner

Publication date 7 October 2020

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.11181

zbMATH Keywords

asymptoticsAiry functionbijectionDyck pathsdirected acyclic graphsminimal automatastretched exponentialfinite languagescompacted trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38)

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$ grows asymptotically like ${\displaystyle }$Thetaleft( n! , 4^n e^{3a_1n^{1/3}} n^{3/4} ight),${\displaystyle }$ where $a_{1}approx-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. 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.

Recommendations

• Asymptotic enumeration of compacted binary trees of bounded right height
• scientific article; zbMATH DE number 3995070
• Compaction for two models of logarithmic‐depth trees: Analysis and experiments
• scientific article; zbMATH DE number 5279360
• scientific article; zbMATH DE number 177816

Cites work

• scientific article; zbMATH DE number 2186886 (Why is no real title available?)
• scientific article; zbMATH DE number 3645067 (Why is no real title available?)
• scientific article; zbMATH DE number 5605090 (Why is no real title available?)
• scientific article; zbMATH DE number 4039297 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 177816 (Why is no real title available?)
• scientific article; zbMATH DE number 2068873 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• 1324-avoiding permutations revisited
• A bijection of plane increasing trees with relaxed binary trees of right height at most one
• A determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata
• Analysis of series expansions for non-algebraic singularities
• Analytic combinatorics
• Asymptotic behavior and the moderate deviation principle for the maximum of a Dyck path
• Asymptotic enumeration of compacted binary trees of bounded right height
• Asymptotic enumeration of minimal automata
• Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language
• Compressed self-avoiding walks, bridges and polygons
• Enumeration and random generation of accessible automata
• Exact enumeration of acyclic deterministic automata
• Heat kernel asymptotics on the lamplighter group
• IMPROVED BOUNDS ON THE NUMBER OF AUTOMATA ACCEPTING FINITE LANGUAGES
• Numerical studies of Thompson's group \(F\) and related groups
• On \(1324\)-avoiding permutations
• On random walks on wreath products
• On the Coefficients of Power Series having Exponential Singularities (Second Paper)
• XML compression via directed acyclic graphs

Cited in

(10)

• scientific article; zbMATH DE number 177816 (Why is no real title available?)
• On the critical exponents of generalized ballot sequences in three dimensions and large tandem walks
• Asymptotic enumeration of compacted binary trees of bounded right height
• On the asymptotic growth of the number of tree-child networks
• Weakly binary expansions of dense meet‐trees
• Young tableaux with periodic walls: counting with the density method
• Enumerative and distributional results for \(d\)-combining tree-child networks
• Compaction for two models of logarithmic‐depth trees: Analysis and experiments
• Block languages and their bitmap representations
• scientific article; zbMATH DE number 3995070 (Why is no real title available?)

This page was built for publication: Compacted binary trees admit a stretched exponential

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2005184)