Ranking and formal power series. (English) Zbl 0721.68023

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.


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q45 Formal languages and automata
Full Text: DOI


[1] Beame, P.W.; Cook, S.A.; Hoover, H.J., Log depth circuits for division and related problems, SIAM J. comput., 15, 994-1003, (1986) · Zbl 0619.68047
[2] Berstel, J., Transductions and context-free languages, (1979), J.B. Teubner Stuttgart · Zbl 0424.68040
[3] Berstel, J.; Reutenauer, C., Rational series and their languages, (1988), Springer Berlin · Zbl 0668.68005
[4] Bertoni, A.; Goldwurm, M.; Sabadini, N., The complexity of computing the number of strings of given length in context-free languages, (), Theoret. Comput. Sci.to appear. · Zbl 0634.68069
[5] Bertoni, A.; Goldwurm, M.; Massazza, P., Counting functions and formal series in noncommuting variables, Inform. process. lett., 34, 117-121, (1990) · Zbl 0695.68053
[6] Cook, S.A., A taxonomy of problems with fast parallel algorithms, Inform. and control, 64, 2-22, (1985) · Zbl 0575.68045
[7] Goldberg, A.V.; Sipser, M., Compression and ranking, Proc. 7th ACM symp. on theory of computing, 440-448, (1985)
[8] Huynh, D.T., The complexity of ranking, Proc. 3rd ann. conf. on structure in complexity theory, 204-212, (1988)
[9] Reif, J.H., Logarithmic depth circuits for algebraic functions, SIAM J. comput., 15, 231-242, (1986) · Zbl 0611.68014
[10] Ruzzo, W.L., On uniform circuit complexity, J. comput. system sci., 22, 365-383, (1981) · Zbl 0462.68013
[11] Salomaa, A.; Soittola, M., Automata theoretic aspects of formal power series, (1978), Springer Berlin · Zbl 0377.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.