Grammar-Oriented Enumeration of Arbitrary Trees and Arbitrary k-ary Trees
Summary :
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)).
- Publication
- IEICE TRANSACTIONS on Information Vol.E82-D No.9 pp.1245-1253
- Publication Date
- 1999/09/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithm and Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Limin XIANG, Kazuo USHIJIMA, "Grammar-Oriented Enumeration of Arbitrary Trees and Arbitrary k-ary Trees" in IEICE TRANSACTIONS on Information,
vol. E82-D, no. 9, pp. 1245-1253, September 1999, doi: .
Abstract: 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)).
URL: https://global.ieice.org/en_transactions/information/10.1587/e82-d_9_1245/_p
Copy
@ARTICLE{e82-d_9_1245,
author={Limin XIANG, Kazuo USHIJIMA, },
journal={IEICE TRANSACTIONS on Information},
title={Grammar-Oriented Enumeration of Arbitrary Trees and Arbitrary k-ary Trees},
year={1999},
volume={E82-D},
number={9},
pages={1245-1253},
abstract={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)).},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - Grammar-Oriented Enumeration of Arbitrary Trees and Arbitrary k-ary Trees
T2 - IEICE TRANSACTIONS on Information
SP - 1245
EP - 1253
AU - Limin XIANG
AU - Kazuo USHIJIMA
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E82-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 1999
AB - 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)).
ER -
English
