Elvey Price, Andrew; Fang, Wenjie; Wallner, Michael Compacted binary trees admit a stretched exponential. (English) Zbl 1448.05034 J. Comb. Theory, Ser. A 177, Article ID 105306, 40 p. (2021). Summary: 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 \[ \Theta ( n ! 4^n e^{3 a_1 n^{1 / 3}} n^{3 / 4} ), \] 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 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. Cited in 2 ReviewsCited in 3 Documents MSC: 05C05 Trees 05C20 Directed graphs (digraphs), tournaments 05C38 Paths and cycles 05C85 Graph algorithms (graph-theoretic aspects) 68Q45 Formal languages and automata Keywords:Airy function; asymptotics; bijection; compacted trees; directed acyclic graphs; Dyck paths; finite languages; minimal automata; stretched exponential PDFBibTeX XMLCite \textit{A. Elvey Price} et al., J. Comb. Theory, Ser. A 177, Article ID 105306, 40 p. (2021; Zbl 1448.05034) Full Text: DOI arXiv Online Encyclopedia of Integer Sequences: Number of deterministic completely defined initially connected acyclic automata with 2 inputs and n transient unlabeled states (and a unique absorbing state). References: [1] Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, National Bureau of Standards Applied Mathematics Series, vol. 55 (1964), For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C. · Zbl 0171.38503 [2] Bassino, F.; David, J.; Sportiello, A., Asymptotic enumeration of minimal automata, (29th International Symposium on Theoretical Aspects of Computer Science. 29th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 14 (2012), Schloss Dagstuhl. Leibniz-Zent. Inform.: Schloss Dagstuhl. Leibniz-Zent. Inform. Wadern), 88-99 · Zbl 1245.68118 [3] Bassino, F.; Nicaud, C., Enumeration and random generation of accessible automata, Theor. Comput. Sci., 381, 1-3, 86-104 (2007) · Zbl 1188.68168 [4] Beaton, N. R.; Guttmann, A. J.; Jensen, I.; Lawler, G. F., Compressed self-avoiding walks, bridges and polygons, J. Phys. A, 48, 45, Article 454001 pp. (Oct. 2015) [5] Bousquet-Mélou, M.; Lohrey, M.; Maneth, S.; Noeth, E., XML compression via directed acyclic graphs, Theory Comput. Syst., 57, 4, 1322-1371 (2015) · Zbl 1352.68079 [6] Callan, D., A determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata, Discrete Math. Theor. Comput. Sci., 10, 2, 77-86 (2008) · Zbl 1196.05008 [7] Conway, A. R.; Guttmann, A. J., On 1324-avoiding permutations, Adv. Appl. Math., 64, 50-69 (2015) · Zbl 1306.05004 [8] Conway, A. R.; Guttmann, A. J.; Zinn-Justin, P., 1324-avoiding permutations revisited, Adv. Appl. Math., 96, 312-333 (2018) · Zbl 1383.05005 [9] Domaratzki, M., Combinatorial interpretations of a generalization of the Genocchi numbers, J. Integer Seq., 7, 3, 11 (2004), Article 04.3.6 · Zbl 1092.11010 [10] Domaratzki, M., Improved bounds on the number of automata accepting finite languages, Computing and Combinatorics Conference. Computing and Combinatorics Conference, COCOON’02. Computing and Combinatorics Conference. Computing and Combinatorics Conference, COCOON’02, Int. J. Found. Comput. Sci., 15, 1, 143-161 (2004) · Zbl 1101.68650 [11] Domaratzki, M., Enumeration of formal languages, Bull. Eur. Assoc. Theor. Comput. Sci., 89, 117-133 (2006) · Zbl 1169.68466 [12] Domaratzki, M.; Kisman, D.; Shallit, J., On the number of distinct languages accepted by finite automata with n states, J. Autom. Lang. Comb., 7, 4, 469-486 (2002) · Zbl 1137.68421 [13] Elvey Price, A.; Fang, W.; Wallner, M., Asymptotics of minimal deterministic finite automata recognizing a finite binary language, (AofA 2020. AofA 2020, LIPIcs, vol. 159 (2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik), 11:1-11:13 [14] Elvey Price, A.; Guttmann, A. J., Numerical studies of Thompson’s group F and related groups, Int. J. Algebra Comput., 29, 2, 179-243 (2019) · Zbl 1515.20235 [15] Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1165.05001 [16] Flajolet, P.; Sipala, P.; Steyaert, J.-M., Analytic variations on the common subexpression problem, (Automata, Languages and Programming. Automata, Languages and Programming, Coventry, 1990. Automata, Languages and Programming. Automata, Languages and Programming, Coventry, 1990, Lecture Notes in Comput. Sci., vol. 443 (1990), Springer: Springer New York), 220-234 · Zbl 0765.68048 [17] Genitrini, A.; Gittenberger, B.; Kauers, M.; Wallner, M., Asymptotic enumeration of compacted binary trees of bounded right height, J. Comb. Theory, Ser. A, 172, Article 105177 pp. (2020) · Zbl 1433.05154 [18] Guttmann, A. J., Analysis of series expansions for non-algebraic singularities, J. Phys. A, 48, 4, Article 045209 pp. (2015) · Zbl 1328.82030 [19] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Series in Computer Science (1979), Addison-Wesley Publishing Co.: Addison-Wesley Publishing Co. Reading, Mass. · Zbl 0426.68001 [20] Korshunov, A. D., Enumeration of finite automata, Probl. Kibern., 34, 5-82 (1978), (In Russian) [21] Korshunov, A. D., On the number of nonisomorphic strongly connected finite automata, Elektron. Inf.verarb. Kybern., 22, 9, 459-462 (1986) · Zbl 0637.68054 [22] Kousha, T., Asymptotic behavior and the moderate deviation principle for the maximum of a Dyck path, Stat. Probab. Lett., 82, 2, 340-347 (2012) · Zbl 1241.60013 [23] Liskovets, V. A., Exact enumeration of acyclic deterministic automata, Discrete Appl. Math., 154, 3, 537-551 (2006) · Zbl 1090.68060 [24] Pittet, C.; Saloff-Coste, L., On random walks on wreath products, Ann. Probab., 30, 2, 948-977 (2002) · Zbl 1021.60004 [25] Revelle, D., Heat kernel asymptotics on the lamplighter group, Electron. Commun. Probab., 8, 142-154 (2003) · Zbl 1061.60112 [26] Wallner, M., A bijection of plane increasing trees with relaxed binary trees of right height at most one, Theor. Comput. Sci., 755, 1-12 (2019) · Zbl 1441.05051 [27] Wallner, M. (2020) [28] Wright, E. M., The coefficients of a certain power series, J. Lond. Math. Soc., 7, 4, 256-262 (1932) · JFM 58.0306.02 [29] Wright, E. M., On the coefficients of power series having exponential singularities, J. Lond. Math. Soc., 8, 1, 71-79 (1933) · JFM 59.0383.01 [30] Wright, E. M., On the coefficients of power series having exponential singularities. II, J. Lond. Math. Soc., 24, 304-309 (1949) · Zbl 0034.34202 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.