Compacted binary trees admit a stretched exponential
From MaRDI portal
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 grows asymptotically like Thetaleft( n! , 4^n e^{3a_1n^{1/3}} n^{3/4}
ight), where 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 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
Cites work
- 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
- 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?)
- 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
(15)- On the critical exponents of generalized ballot sequences in three dimensions and large tandem walks
- On the asymptotic growth of the number of tree-child networks
- Asymptotic enumeration of compacted binary trees of bounded right height
- Young tableaux with periodic walls: counting with the density method
- scientific article; zbMATH DE number 177816 (Why is no real title available?)
- scientific article; zbMATH DE number 3995070 (Why is no real title available?)
- Compaction for two models of logarithmic‐depth trees: Analysis and experiments
- Weakly binary expansions of dense meet‐trees
- Enumerative and distributional results for d-combining tree-child networks
- Block languages and their bitmap representations
- Asymptotic analysis and efficient random sampling of directed ordered acyclic graphs
- Asymptotics of relaxed k-ary trees
- Galled tree-child networks
- Progressive and rushed Dyck paths
- On naturally labelled posets and permutations avoiding 12--34
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)
