Chiang Mai Journal of Science

                A string s of length 2n is called a well-formed parenthesis string (w.f.p. string for short), if it consists of n left parentheses than left parentheses. W.f.p. strings are represented in the literature by different types of integer sequences including P-, X-, and T-sequences. In this paper, we introduce a new class of sequences, called L-sequences, which originates from the so-called RD-sequences for representing k-ary trees and their generalization, called  non-regular trees. This paper deals with the ranking and unranking of w.f.p. strings in lexicographic order under these representations. We give linear-time transformations between L-sequences and other type of sequences, and design linear time ranking and unranking algorithms for all these sequence types.