Grammar-Oriented Enumeration of Arbitrary Trees and Arbitrary k-ary Trees


IEICE TRANSACTIONS on Information and Systems   Vol.E82-D   No.9   pp.1245-1253
Publication Date: 1999/09/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
grammar,  trees,  k-ary trees,  enumeration,  lexicographic,  

Full Text: PDF(2.1MB)>>
Buy this Article

In literature, many methods have been presented for enumerating binary trees (full binary trees) and regular k-ary trees, while no one for enumerating arbitrary trees or arbitrary k-ary trees. It is proposed in 1997 using a context-free grammar GBT (GFBT) to code binary trees (full binary trees) for enumerating them. In this paper, we use another grammar GT (GTk) to code arbitrary trees (arbitrary k-ary trees) for enumerating them. The properties of words of Ln(GT) (Ln(GTk)) are discussed in depth, including necessary and sufficient conditions for a word, prefix and suffix of Ln(GT) (Ln(GTk)), and efficient algorithms are given and analyzed for the enumeration of words of Ln(GT) (Ln(GTk)).