Counting problems and algebraic formal power series in noncommuting variables. (English) Zbl 0695.68053

Summary: We study the complexity of certain counting functions related to formal power series in noncommuting variables. We prove that, for every algebraic formal power series in \({\mathbb{Z}}<<\Sigma >>\), the problem of computing the corresponding counting function is \(NC^ 1\)-reducible to integer division. As a consequence, for every unambiguous context-free language \(L\subseteq \Sigma^*\), the problem of computing #\(\{\) \(x\in L: | x| =n\}\) is also \(NC^ 1\)-reducible to integer division. Therefore all these counting problems are solvable by families of log- space uniform Boolean circuits of depth O(log n log log n) and polynomial size.


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
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] Bertoni, A.; Goldwurm, M.; Sabadini, N., Computing the counting functions of context-free languages, (), 167-179, Lecture Notes in Computer Science · Zbl 0634.68069
[3] A. Bertoni, M. Goldwurm and N. Sabadini, The complexity of computing the number of strings of given length in context-free languages, Theoret. Comput. Sci., to appear. · Zbl 0744.68066
[4] Chomsky, N.; Sch├╝tzenberger, M.P., The algebraic theory of context free languages, (), 118-161 · Zbl 0148.00804
[5] Cook, S.A., A taxonomy of problems with fast parallel algorithms, Inform. and control, 64, 2-22, (1985) · Zbl 0575.68045
[6] Cori, R.; Vauquelin, B., Planar maps are well labeled trees, Canad. J. math., 33, 1023-1042, (1981) · Zbl 0415.05020
[7] Delest, M.P.; Viennot, G., Algebraic languages and polyominoes enumeration, Theoret. comput. sci., 34, 169-206, (1984) · Zbl 0985.68516
[8] Flajolet, P., Analytic models and ambiguity of context-free languages, Theoret. comput. sci., 49, 283-309, (1987) · Zbl 0612.68069
[9] Goldberg, A.V.; Sipser, M., Compression and ranking, Proc. 7th ACM symp. on theory of computing, 440-448, (1985)
[10] Goldman, J.R., Formal languages and enumeration, J. combin. theory ser. A, 24, 318-338, (1978) · Zbl 0411.05010
[11] Goulden, I.P.; Jackson, D.M., Combinatorial enumeration, (1983), Wiley New York · Zbl 0519.05001
[12] Huynh, D.T., The complexity of ranking, Proc. 3rd annual conference on structure in complexity theory, 204-212, (1988)
[13] Reif, J.H., Logarithmic depth circuits for algebraic functions, SIAM J. comput., 15, 231-242, (1986) · Zbl 0611.68014
[14] Salomaa, A.; Soittola, M., Automata theoretic aspects of formal power series, (1978), Springer New York · Zbl 0377.68039
[15] Valiant, L.G., The complexity of enumeration and reliability problems, SIAM J. comput., 8, 410-421, (1979) · Zbl 0419.68082
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.