Table of Links
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.
This paper is