Ranking and formal power series (Q2641104)

The ranking problem for a language \(L\subseteq A^*\) is the following: given w in L, compute the integer n such that w is the n-th element of L for the lexicographic order (u\(\leq v\) if either \(| u| <| v|\) or \(| u| =| v|\) and u precedes v alphabetically). The value problem for noncommutative formal series \(S\epsilon {\mathbb{N}}\ll X\gg\) is the following: given w in \(X^*\), compute the coefficient of w in S. The authors show that the ranking problem for an unambiguous context-free language is \(NC^ 1\)-reducible to the value problem for an algebraic formal series. An application to regular languages is given.