Geodesic
Ranking and Unranking of a Generalized Dyck Language and the Application to the Generation of Random Trees
Séminaire lotharingien de combinatoire, Tome 43 (1999-2000)

Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website

Given two disjoint alphabets of opening and closing brackets and a relation describing the pairs of brackets that can be used, the generalized Dyck language consists of all Dyck words that contain only pairs of brackets decribed by the relation.

If the Dyck words are arranged according to the lexicographical order, then ranking means to determine the rank, i. e. the position, of a Dyck word. Unranking creates the Dyck word from its position.

We present a ranking and an unranking algorithm for the generalized Dyck language. Given a Dyck word, the ranking algorithm reads a prefix as short as possible to compute the rank. Thus, this algorithm is optimal. The unranking algorithm creates the Dyck word symbol by symbol from left to right.

Further, we analyze the ranking algorithm. For the computation of the rank of a Dyck word for arbitrary relation, we compute the moments of the random variable describing the length of the prefix to be read. No computation is necessary for the analysis of the unranking algorithm, because the whole Dyck word has to be created.

The generalized Dyck language can be used for the coding of trees. Not only the shape of the tree is coded but also its labels of the nodes and/or edges. The algorithms discussed here can be used for the ranking and unranking of different types of trees. With a random number generator and the unranking algorithm we are able to generate random trees with diverse properties. Some classes of labelled trees will be discussed.

Keywords: Dyck language, random trees, ranking, unranking, lexicographical order, one-to-one correspondence, average-case analysis. 

@article{SLC_1999-2000_43_a1,
     author = {Jens Liebehenschel},
     title = {Ranking and {Unranking} of a {Generalized} {Dyck} {Language} and the {Application} to the {Generation} of {Random} {Trees}},
     journal = {S\'eminaire lotharingien de combinatoire},
     publisher = {mathdoc},
     volume = {43},
     year = {1999-2000},
     url = {http://geodesic.mathdoc.fr/item/SLC_1999-2000_43_a1/}
}
TY  - JOUR
AU  - Jens Liebehenschel
TI  - Ranking and Unranking of a Generalized Dyck Language and the Application to the Generation of Random Trees
JO  - Séminaire lotharingien de combinatoire
PY  - 1999-2000
VL  - 43
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SLC_1999-2000_43_a1/
ID  - SLC_1999-2000_43_a1
ER  - 
%0 Journal Article
%A Jens Liebehenschel
%T Ranking and Unranking of a Generalized Dyck Language and the Application to the Generation of Random Trees
%J Séminaire lotharingien de combinatoire
%D 1999-2000
%V 43
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SLC_1999-2000_43_a1/
%F SLC_1999-2000_43_a1
Jens Liebehenschel. Ranking and Unranking of a Generalized Dyck Language and the Application to the Generation of Random Trees. Séminaire lotharingien de combinatoire, Tome 43 (1999-2000). http://geodesic.mathdoc.fr/item/SLC_1999-2000_43_a1/