Algorithm for ranking members of a regular language?

Question

A little while back, I was reading a paper that mentioned a method for computing an integer 'rank' for a particular string $s \in L$ where $L$ is some regular language. This rank uniquely determines any string in the language and has the property that, for some lexicographic ordering, $s_1 < s_2 \implies rank(s_1) < rank(s_2)$. Another property is that given $rank(s_0)$ we can efficiently determine $s_0$ using an 'unrank' algorithm.

However, the paper wasn't very specific and I don't know where to find a more detailed description of the algorithm. Can anyone point me in the right direction?

I remember that it involves compiling a regular expression to a DFA and giving the description of the DFA to the ranking algorithm.

Thanks for your help.

Answer 1

Let $A = \{1, ..., k\}$ be an ordered alphabet. Then each word on $A^*$ can be viewed as a number in base $k + 1$ (note that $0$ is never used on purpose). Now define $$ rank(u) = \begin{cases} u &\text{if $u \in L$} \\ 0 &\text{otherwise} \end{cases} $$ Then $rank$ preserves the shortlex (or radix) order, which is the order $\leqslant$ on $A^*$ defined by $u \leqslant v$ if and only if $|u| < |v|$ or $|u| = |v|$ and $u \leqslant_{lex} v$. That is, words are first ordered by length and words of equal length are ordered according to the lexicographic order. Now, if $L$ is regular, $rank$ is easy to compute and is of course one-to-one on $L$.

Answer 2

This is another classical example of inductive enumeration. I assume that we are given some DFA for the language $L$ over an ordered alphabet $\Sigma$. Let's start with the easier case of words of length $n$. Using linear algebra, given a prefix $w$, we can compute efficiently $N(w,m) = |\{ x \in \Sigma^m : wx \in L\}|$. Define $N(m) = N(\epsilon,m)$ for short (this is the number of words of length $m$). We define the code $C'(w)$ of a word $w \in L$ as follows: $$ C'(a_1\cdots a_n) = \sum_{i=1}^n \sum_{b < a_i} N(a_1\cdots a_{i-1} b,n-i). $$ In order to code words of arbitrary length, we simply use the formula $$ C(w) = \sum_{n<|w|} N(n) + C'(w). $$ It is straightforward to compute the inverse of this encoding. This encoding deviates from your specification by ordering first according to length and only then lexicographically, but as dkuper mentions this is unavoidable if you want your range to be $\omega$ rather than a more exotic linear order.

There could be a "trick" which allows using simpler formulas in this particular case, but this is the basic idea.

Answer 3

To add to Yuval's answer, and provide references:

If you want more references regarding the complexity of ranking different classes of sets, here are some places to look:

A. Goldberg and M. Sipser, Compression and ranking. SIAM J. Comput. 20 (1991), 524-536.

L. Hemachandra and S. Rudich, On the complexity of ranking. J. Comput. System Sci. 41 (1990), 251-271.

E. Allender,Danilo Bruschi and Giovanni Pighizzini, The complexity of computing maximal word functions, Computational Complexity 3, 1993, pp. 368-391.

There are also a few minor results in a chapter in my thesis on ranking, available as the bottom-most publication on the list here: http://www.cs.rutgers.edu/~allender/publications/complete_list.html