<p>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 &lt; 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&lt;|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.</p>

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

CC BY-SA 3.0
2013-08-09T05:42:06.007Z
2013-08-09T05:42:06.007Z
Yuval Filmus
<p>To add to Yuval's answer, and provide references:</p>

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

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

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

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

<p>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: <a href="http://www.cs.rutgers.edu/~allender/publications/complete_list.html">http://www.cs.rutgers.edu/~allender/publications/complete_list.html</a></p>

CC BY-SA 3.0
2013-08-14T01:07:48.820Z
2013-08-14T01:07:48.820Z
Eric Allender
<p>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 &amp;\text{if $u \in L$} \\
0 &amp;\text{otherwise}
\end{cases}
$$
Then $rank$ preserves the <em>shortlex</em> (or <em>radix</em>) order, which is the order $\leqslant$ on $A^*$ defined by $u \leqslant v$ if and only if $|u| &lt; |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$.</p>

CC BY-SA 3.0
2013-08-09T11:08:39.767Z
2013-08-09T11:08:39.767Z
J.-E. Pin
<p>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 &lt; s_2 \implies rank(s_1) &lt; rank(s_2)$. Another property is that given $rank(s_0)$ we can efficiently determine $s_0$ using an 'unrank' algorithm.</p>

<p>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? </p>

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

<p>Thanks for your help.</p>

CC BY-SA 3.0
2013-08-09T01:46:09.707Z
it seems impossible, because there are infinitely many words $w$ such that $a<_{lex}w<_{lex}b$, so it is impossible to choose $\mathit{rank}(a)$ and $\mathit{rank}(b)$ in a coherent way.
Denis
CC BY-SA 3.0
2013-08-09T14:59:07.477Z
doesnt [weighted FSMs](http://en.wikipedia.org/wiki/Finite_state_transducer#Weighted_automata) fit this? weighted FSMs have been used extensively in speech recognition. see also [AT&T fsm library](http://en.wikipedia.org/wiki/AT%26T_FSM_Library) which handles them.
vzn
CC BY-SA 3.0
2013-08-13T07:19:06.503Z
Are you sure it's an integer rank?  There are many choices for this if you use ordinals to rank sentences.
Charles Stewart
CC BY-SA 3.0
2013-08-13T16:30:44.730Z
Ordinals, you mean like the natural numbers? Yeah that's what I meant, obviously it's nonsensical for strings to have a negative rank.
pg1989
<fl.formal-languages><automata-theory><regular-language><regular-expressions>
Algorithm for ranking members of a regular language?
pg1989
# Algorithm for ranking members of a regular language?

(Asked by: username_0 on 2013-08-09)

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.

**Tags:** fl.formal-languages, automata-theory, regular-language, regular-expressions
> **Comments:**
> **username_1**: it seems impossible, because there are infinitely many words $w$ such that $a<_{lex}w<_{lex}b$, so it is impossible to choose $\mathit{rank}(a)$ and $\mathit{rank}(b)$ in a coherent way.  
> **username_2**: doesnt [weighted FSMs](http://en.wikipedia.org/wiki/Finite_state_transducer#Weighted_automata) fit this? weighted FSMs have been used extensively in speech recognition. see also [AT&T fsm library](http://en.wikipedia.org/wiki/AT%26T_FSM_Library) which handles them.  
> **username_3**: Are you sure it's an integer rank?  There are many choices for this if you use ordinals to rank sentences.  
> **username_0**: Ordinals, you mean like the natural numbers? Yeah that's what I meant, obviously it's nonsensical for strings to have a negative rank.  

---

## 3 answers

### Answer by username_6 on 2013-08-09. Score: 14 | Accepted answer

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 by username_4 on 2013-08-09. Score: 7

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 by username_5 on 2013-08-14. Score: 7

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>


---

