Các Cây Con Biên Phân Biệt Trong Các Cây Ngẫu Nhiên

Abiteboul, S., Bourhis, P., Vianu, V.: Highly expressive query languages for unordered data trees. Theory of Comput. Syst. 57(4), 927–966 (2015). https://doi.org/10.1007/s00224-015-9617-5

Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools. Addison-Wesley series in computer science / World student series edition. Addison-Wesley, Reading, MA, USA (1986)

Aldous, D.: Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1(2), 228–266 (1991). https://doi.org/10.1214/aoap/1177005936

Artin, M.: Algebra. Pearson Prentice Hall, Upper Saddle River, NJ, USA (2011)

Bergeron, F., Flajolet, P., Salvy, B.: Varieties of increasing trees. In: CAAP ’92 (Rennes, 1992), Lecture Notes in Comput. Sci., vol. 581, pp. 24–48. Springer, Berlin (1992). https://doi.org/10.1007/3-540-55251-0_2

Bodini, O., Genitrini, A., Gittenberger, B., Larcher, I., Naima, M.: Compaction for two models of logarithmic-depth trees: Analysis and experiments. Random Struct. Algorithms 61(1), 31–61 (2022). https://doi.org/10.1002/rsa.21056

Bóna, M., Flajolet, P.: Isomorphism and symmetries in random phylogenetic trees. J. Appl. Probab. 46(4), 1005–1019 (2009). https://doi.org/10.1239/jap/1261670685

Boneva, I., Ciucanu, R., Staworko, S.: Schemas for unordered XML on a DIME. Theory of Compuing Systems 57(2), 337–376 (2015). https://doi.org/10.1007/s00224-014-9593-1

Bousquet-Mélou, M., Lohrey, M., Maneth, S., Noeth, E.: XML compression via DAGs. Theory of Comput. Syst. 57(4), 1322–1371 (2015)

Bryant, R.E.: Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Comput. Surv. 24(3), 293–318 (1992)

Buneman, P., Grohe, M., Koch, C.: Path queries on compressed XML. In: J.C. Freytag, et al. (eds.) Proceedings of the 29th Conference on Very Large Data Bases, VLDB 2003, pp. 141–152. Morgan Kaufmann (2003)

Cai, X.S.: A study of large fringe and non-fringe subtrees in conditional galton-watson trees. Ph.D. thesis, McGill University (2016)

Dennert, F., Grübel, R.: On the subtree size profile of binary search trees. Comb. Probab. Comput. 19(4), 561–578 (2010). https://doi.org/10.1017/S0963548309990630

Devroye, L.: On the richness of the collection of subtrees in random binary search trees. Inf. Process. Lett. 65(4), 195–199 (1998)

Devroye, L., Janson, S.: Protected nodes and fringe subtrees in some random trees. Electron. Commun. Probab. 19, 1–10 (2014). https://doi.org/10.1214/ECP.v19-3048

Drmota, M.: Random Trees: An Interplay Between Combinatorics and Probability, 1st edn. Springer, Vienna, Austria (2009)

Feng, Q., Mahmoud, H.M.: On the variety of shapes on the fringe of a random recursive tree. J. Appl. Probab. 47(1), 191–200 (2010). https://doi.org/10.1239/jap/1269610825

Fill, J.A., Kapur, N.: Limiting distributions for additive functionals on Catalan trees. Theoret. Comput. Sci. 326(1–3), 69–102 (2004). https://doi.org/10.1016/j.tcs.2004.05.010

Finch, S.R.: Mathematical Constants. Encyclopedia of Mathematics and its Applications 94. Cambridge University Press (2003). https://www.cambridge.org/academic/subjects/mathematics/recreationalmathematics/mathematical-constants

Flajolet, P., Gourdon, X., Martínez, C.: Patterns in random binary search trees. Random Structures & Algorithms 11(3), 223–244 (1997)

Flajolet, P., Sedgewick, R.: Mellin transforms and asymptotics: finite differences and Rice’s integrals. Theoret. Comput. Sci. 144(1–2), 101–124 (1995). https://doi.org/10.1016/0304-3975(94)00281-M. Special volume on mathematical analysis of algorithms

Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press (2009). https://www.cambridge.org/core/books/analytic-combinatorics/7E37474C43E9B95C90BEDE082CF28708

Flajolet, P., Sipala, P., Steyaert, J.M.: Analytic variations on the common subexpression problem. In: Proceedings of the 17th International Colloquium on Automata, Languages and Programming, ICALP 1990, Lecture Notes in Computer Science, vol. 443, pp. 220–234. Springer (1990)

Frick, M., Grohe, M., Koch, C.: Query evaluation on compressed trees (extended abstract). In: Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, LICS 2003, pp. 188–197. IEEE Computer Society Press (2003)

Fuchs, M.: Limit theorems for subtree size profiles of increasing trees. Comb. Probab. Comput. 21(3), 412–441 (2012). https://doi.org/10.1017/S096354831100071X

Ganardi, M., Hucke, D., Lohrey, M., Benkner, L.S.: Universal tree source coding using grammar-based compression. IEEE Trans. Inf. Theory 65(10), 6399–6413 (2019). https://doi.org/10.1109/TIT.2019.2919829

Gut, A.: Probability: A Graduate Course. Springer, New York (2005)

Holmgren, C., Janson, S., Šileikis, M.: Multivariate normal limit laws for the numbers of fringe subtrees in $$m$$-ary search trees and preferential attachment trees. Electron. J. Combin. 24(2), Paper No. 2.51, 49 pp. (2017). https://doi.org/10.37236/6374

Janson, S.: Random cutting and records in deterministic and random trees. Random Structures & Algorithms 29(2), 139–179 (2006). https://doi.org/10.1002/rsa.20086. https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20086

Janson, S.: Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. Probab. Surv. 9, 103–252 (2012). https://doi.org/10.1214/11-PS188

Janson, S.: Asymptotic normality of fringe subtrees and additive functionals in conditioned galton-watson trees. Random Struct. Algorithms 48(1), 57–101 (2016). https://doi.org/10.1002/rsa.20568

Jordan, C.: Sur les assemblages de lignes. Journal für die reine und angewandte Mathematik 70, 185–190 (1869)

Kieffer, J.C., Yang, E.H., Szpankowski, W.: Structural complexity of random binary trees. In: Proceedings of the 2009 IEEE International Symposium on Information Theory, ISIT 2009, pp. 635–639. IEEE (2009)

Knuth, D.E.: The Art of Computer Programming, vol. 3. Addison-Wesley, Reading, MA (1998)

Kolchin, V.F.: Random mappings / Valentin F. Kolchin. Translations series in mathematics and engineering. Optimization Software, New York (1986)

Lohrey, M., Maneth, S., Reh, C.P.: Compression of unordered XML trees. In: 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, pp. 18:1–18:17 (2017). https://doi.org/10.4230/LIPIcs.ICDT.2017.18

Meir, A., Moon, J.W.: On the altitude of nodes in random trees. Can. J. Math. 30(5), 997–1015 (1978). https://doi.org/10.4153/CJM-1978-085-0

Olsson, C., Wagner, S.: Automorphisms of random trees. In: 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, LIPIcs. Leibniz Int. Proc. Inform., vol. 225, pp. 16:1–16:16. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2022)

Otter, R.: The number of trees. Ann. of Math. 2(49), 583–599 (1948). https://doi.org/10.2307/1969046

Panholzer, A., Prodinger, H.: Level of nodes in increasing trees revisited. Random Structures Algorithms 31(2), 203–226 (2007). https://doi.org/10.1002/rsa.20161

Paterson, M., Wegman, M.N.: Linear unification. J. Comput. Syst. Sci. 16(2), 158–167 (1978)

Ralaivaosaona, D., Wagner, S.: A central limit theorem for additive functionals of increasing trees. Combin. Probab. Comput. 28(4), 618–637 (2019). https://doi.org/10.1017/s0963548318000585

Ralaivaosaona, D., Wagner, S.G.: Repeated fringe subtrees in random rooted trees. In: Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2015, pp. 78–88. SIAM (2015)

Ruskey, F.: Generating linear extensions of posets by transpositions. J. Combin. Theory Ser. B 54(1), 77–101 (1992)

Seelbach Benkner, L., Lohrey, M.: Average case analysis of leaf-centric binary tree sources. In: 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, pp. 16:1–16:15 (2018). https://doi.org/10.4230/LIPIcs.MFCS.2018.16

Seelbach Benkner, L., Wagner, S.G.: On the collection of fringe subtrees in random binary trees. In: Y. Kohayakawa, F.K. Miyazawa (eds.) LATIN 2020: Theoretical Informatics - 14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12118, pp. 546–558. Springer (2020). https://doi.org/10.1007/978-3-030-61792-9_43

Zhang, J., Yang, E.H., Kieffer, J.C.: A universal grammar-based code for lossless compression of binary trees. IEEE Trans. Inf. Theory 60(3), 1373–1386 (2014)

Zhang, S., Du, Z., Wang, J.T.: New techniques for mining frequent patterns in unordered trees. IEEE Transactions on Cybernetics 45(6), 1113–1125 (2015). https://doi.org/10.1109/TCYB.2014.2345579