|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc020402,
author = {Jens Liebehenschel},
title = {Ranking and Unranking of Lexicographically Ordered Words:
an Average-Case Analysis},
journal = jalc,
year = 1997,
volume = 2,
number = 4,
pages = {227--268},
keywords = {ranking, unranking, lexicographical order,
average-case analysis, regular languages, permutations,
subsets, Dyck language, Motzkin language, trees},
abstract = {We consider all words of length $n$ of a formal language.
If these words are arranged according to the lexicographical
order, then ranking means to determine the position of a
word of the language. Unranking is the inverse operation of
ranking. For a given formal language we compute the average
length of the shortest prefix of a word to be read to
determine its position, if the word is read from left to
right. The length of the shortest prefix to be read depends
on the language only, not on the ranking algorithm. After
having derived a general expression, we demonstrate the
result by discussing various concrete applications. Ranking
will be analyzed for regular languages, permutations,
subsets of sets, the Dyck language, the Motzkin language,
extended ordered binary trees according to Zaks, ordered
binary trees according to Er, extended ordered $t$-ary trees
according to Ruskey, ordered trees with bounded height and
Cayley trees. Furthermore, ranking and unranking algorithms
will be presented for the languages aforementioned.}
}