LIPIcs.MFCS.2018.16.pdf
- Filesize: 472 kB
- 15 pages
Document
Average Case Analysis of Leaf-Centric Binary Tree Sources
Authors
-
Part of:
Volume:
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-08-27
Cite AsGet BibTex
Louisa Seelbach Benkner and Markus Lohrey. Average Case Analysis of Leaf-Centric Binary Tree Sources. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.16
https://doi.org/10.4230/LIPIcs.MFCS.2018.16
Abstract
We study the average size of the minimal directed acyclic graph (DAG) with respect to so-called leaf-centric binary tree sources as studied by Zhang, Yang, and Kieffer. A leaf-centric binary tree source induces for every n >= 2 a probability distribution on all binary trees with n leaves. We generalize a result shown by Flajolet, Gourdon, Martinez and Devroye according to which the average size of the minimal DAG of a binary tree that is produced by the binary search tree model is Theta(n / log n).
Subject Classification
ACM Subject Classification
- Mathematics of computing → Enumeration
Keywords
- Directed acylic graphs
- average case analysis
- tree compression
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley series in computer science / World student series edition. Addison-Wesley, 1986.
- Louisa Seelbach Benkner and Markus Lohrey. Average case analysis of leaf-centric binary tree sources. CoRR, abs/1804.10396, 2018. URL: http://arxiv.org/abs/1804.10396.
-
Mireille Bousquet-Mélou, Markus Lohrey, Sebastian Maneth, and Eric Noeth. XML compression via DAGs. Theory of Computing Systems, 57(4):1322-1371, 2015.
-
Randal E. Bryant. Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys, 24(3):293-318, 1992.
-
Peter Buneman, Martin Grohe, and Christoph Koch. Path queries on compressed XML. In Johann Christoph Freytag et al., editors, Proceedings of the 29th Conference on Very Large Data Bases, VLDB 2003, pages 141-152. Morgan Kaufmann, 2003.
-
Luc Devroye. On the richness of the collection of subtrees in random binary search trees. Information Processing Letters, 65(4):195-199, 1998.
-
Philippe Flajolet, Xavier Gourdon, and Conrado Martínez. Patterns in random binary search trees. Random Structures &Algorithms, 11(3):223-244, 1997.
-
Philippe Flajolet, Paolo Sipala, and Jean-Marc Steyaert. Analytic variations on the common subexpression problem. In Proceedings of the 17th International Colloquium on Automata, Languages and Programming, ICALP 1990, volume 443 of Lecture Notes in Computer Science, pages 220-234. Springer, 1990.
-
Markus Frick, Martin Grohe, and Christoph Koch. Query evaluation on compressed trees (extended abstract). In Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, LICS 2003, pages 188-197. IEEE Computer Society Press, 2003.
-
Danny Hucke and Markus Lohrey. Universal tree source coding using grammar-based compression. In Proceedings of the 2017 IEEE International Symposium on Information Theory, ISIT 2017, pages 1753-1757. IEEE, 2017.
-
John C. Kieffer, En-Hui Yang, and Wojciech Szpankowski. Structural complexity of random binary trees. In Proceedings of the 2009 IEEE International Symposium on Information Theory, ISIT 2009, pages 635-639. IEEE, 2009.
-
Donald E. Knuth. The Art of Computer Programming: Volume 3 - Sorting and Searching. Addison-Wesley, 1998.
-
Conrado Martínez. Statistics under the BST model. Dissertation, Universidad Politécnica de Cataluna, 1991.
-
Mike Paterson and Mark N. Wegman. Linear unification. Journal of Computer and System Sciences, 16(2):158-167, 1978.
-
Dimbinaina Ralaivaosaona and Stephan G. Wagner. Repeated fringe subtrees in random rooted trees. In Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2015, pages 78-88. SIAM, 2015.
-
Jie Zhang, En-Hui Yang, and John C. Kieffer. A universal grammar-based code for lossless compression of binary trees. IEEE Transactions on Information Theory, 60(3):1373-1386, 2014.