Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 2. Pairing functions 2. Pairing functions Enumerating trees
LZ-trees
Conclusion and References Enumerating trees Enumerating trees LZ-trees LZ-trees Conclusion and References Conclusion and References 5 Conclusion This work describes a simple algorithm that enumerates the trees generated by a CFG by forming a bijection between these trees and integers. The key abstraction, an IntegerizedStack, allowed us to encode arbitrary information into a single integer through the use of pairing functions. References [1] C. Costa Florencio, J. Daenen, J. Ramon, J. Van den Bussche, and D. Van Dyck, “Naive infinite enumeration of context-free languages in incremental polynomial time,” Journal of Universal Computer Science, vol. 21, no. 7, pp. 891–911, 2015. [2] E. Makinen, “On lexicographic enumeration of regular and context-free languages,” Acta Cybernetica, vol. 13, no. 1, pp. 55–61, 1997. [3] P. Domosi, “Unusual algorithms for lexicographical enumeration,” Acta Cybernetica, vol. 14, no. 3, pp. 461–468, 2000. [4] Y. Dong, “Linear algorithm for lexicographic enumeration of cfg parse trees,” Science in China Series F: Information Sciences, vol. 52, no. 7, pp. 1177–1202, 2009. [5] D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees–History of Combinatorial Generation (Art of Computer Programming). AddisonWesley Professional, 2006. [6] I. Semba, “Generation of all the balanced parenthesis strings in lexicographical order,” Information Processing Letters, vol. 12, no. 4, pp. 188–192, 1981. [7] W. Skarbek, “Generating ordered trees,” Theoretical Computer Science, vol. 57, no. 1, pp. 153–159, 1988. [8] S. Zaks, “Lexicographic generation of ordered trees,” Theoretical Computer Science, vol. 10, no. 1, pp. 63–82, 1980. [9] M. Er, “Enumerating ordered trees lexicographically,” The Computer Journal, vol. 28, no. 5, pp. 538–542, 1985. [10] E. Nagel and J. R. Newman, Godel’s proof. Routledge, 2012. [11] R. M. Smullyan, G¨odel’s incompleteness theorems. Oxford University Press on Demand, 1992. [12] G. Cantor, “Ein beitrag zur mannigfaltigkeitslehre,” Journal f¨ur die reine und angewandte Mathematik (Crelles Journal), vol. 1878, no. 84, pp. 242–258, 1878. [13] M. P. Szudzik, “The rosenberg-strong pairing function,” arXiv preprint arXiv:1706.04129, 2017. [14] M. A. Vsemirnov, “Two elementary proofs of the fueter–polya theorem on pairing polynomials,” Algebra i Analiz, vol. 13, no. 5, pp. 1–15, 2001. [15] P. W. Adriaans, “A simple information theoretical proof of the fueter-p\’olya conjecture,” arXiv preprint arXiv:1809.09871, 2018. [16] K. W. Regan, “Minimum-complexity pairing functions,” Journal of Computer and System Sciences, vol. 45, no. 3, pp. 285–295, 1992. [17] A. Rosenberg and H. Strong, “Addressing arrays by shells,” IBM Technical Disclosure Bulletin, vol. 4, pp. 3026–3028, 1972. [18] M. Johnson, T. L. Griffiths, and S. Goldwater, “Adaptor grammars: A framework for specifying compositional nonparametric bayesian models,” in Advances in neural information processing systems, 2007, pp. 641–648. [19] T. J. O’Donnell, Productivity and reuse in language: A theory of linguistic computation and storage. MIT Press, 2015. [20] J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” IEEE Transactions on information theory, vol. 23, no. 3, pp. 337–343, 1977. Author:
(1) Steven T. Piantadosi. Author: Author: (1) Steven T. Piantadosi. This paper is available on arxiv under CC BY 4.0 license. This paper is available on arxiv under CC BY 4.0 license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Integer-Based CFG Tree Counting: What You Need to Know

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

CFG Tree Enumeration: A Simple Integer-Based Bijection Algorithm

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

CFG Tree Enumeration: A Simple Integer-Based Bijection Algorithm

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps