Ranking and unranking of a generalized Dyck language and the application to the generation of random trees (Q1972222)

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 are discussed.