The complexity of computing the number of strings of given length in context-free languages. (English) Zbl 0744.68066

For a context-free language \(L\), \(f_ L(1^ n)\) denotes the number of strings of length \(n\) belonging to \(L\). The counting function \(f_ L\) is used to study the inherent ambiguity of the context-free languages and to solve enumeration problems.
The paper concerns with the complexity of computing of the counting function \(f_ L\). The main result is proven in the second section and it claims that if \(L\) is an unambiguous context-free language then \(f_ L\) can be computed by a log-space uniform family of Boolean circuits with depth \(O(\log n\log\log n)\) and polynomial size. The third and the fourth sections study the complexity of computing of the function \(f_ L\) by counting Turing machines. In the last section is defined a language of ambiguity degree two for that the counting function \(f_ L\) is \(\# P_ 1\)-complete (\(\# P_ 1\) is the class of all functions \(f: \{1\}^*\to N\) countable in polynomial time by a counting Turing machine).
Reviewer: D.Lucanu (Iaşi)


68Q25 Analysis of algorithms and problem complexity
68W15 Distributed algorithms
68Q45 Formal languages and automata
Full Text: DOI


[1] Baron, G.; Kuich, W., The characterization of nonexpansive grammars by rational power series, Inform. and control, 48, 109-118, (1981) · Zbl 0481.68075
[2] 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
[3] Berkowitz, S.J., On computing the determinant in small parallel time using a small number of processors, Inform. process. lett., 18, 147-150, (1984) · Zbl 0541.68019
[4] Bertoni, A.; Mauri, G.; Sabadini, N., A characterization of the class of functions computable in polynomial time by random access machine, Proc. 13th ACM symp. on theory of computing, 168-176, (1981)
[5] Borodin, A., On relating time and space to size and depth, SIAM J. comput., 6, 733-744, (1977) · Zbl 0366.68039
[6] Chandrasekharan, K., Introduction to analytic number theory, (1968), Springer Berlin · Zbl 0169.37502
[7] Chomsky, N.; Schützenberger, M.P., The algebraic theory of context free languages, (), 118-161 · Zbl 0148.00804
[8] Comtet, L., Calcul pratique des coefficients de Taylor d’une fonction algébrique, Enseign. math., 10, 267-270, (1964) · Zbl 0166.41702
[9] Cook, S.A., Towards a complexity theory of synchronous parallel computation, Enseign. math., 27, 99-124, (1981) · Zbl 0473.68041
[10] Cook, S.A., A taxonomy of problems with fast parallel algorithms, Inform. and control, 64, 2-22, (1985) · Zbl 0575.68045
[11] Cori, R.; Richard, J., Enumération des graphes planaires à l’aide des séries formelles en variables non commutatives, Discrete math., 2, 115-162, (1971) · Zbl 0247.05140
[12] Cori, R.; Vauquelin, B., Planar maps are well labeled trees, Canad. J. math., 33, 1023-1042, (1981) · Zbl 0415.05020
[13] Delest, M.P.; Viennot, G., Algebraic languages and polyominoes enumeration, Theoret. comput. sci., 34, 169-206, (1984) · Zbl 0985.68516
[14] Flajolet, P., Analytic models and ambiguity of context-free languages, Theoret. comput. sci., 49, 283-309, (1987) · Zbl 0612.68069
[15] Goldberg, A.V.; Sipser, M., Compression and ranking, Proc. 7th ACM symp. on theory of computing, 440-448, (1985)
[16] Goldman, J.R., Formal languages and enumeration, J. combin. theory ser. A, 24, 318-338, (1978) · Zbl 0411.05010
[17] Goldwurm, M., Formal series methods in algorithm analysis for problems on languages, Doctoral thesis, (May 1988), Dip. di Scienze dell’Informazione, Università di Milano
[18] Hartmanis, J., Context-free languages and Turing machine computations, Proc. sympos. appl. math., 19, 42-51, (1967) · Zbl 0189.29101
[19] Hartmanis, J.; Immerman, N.; Sewelson, V., Sparse sets in NP - P: EXPTIME versus NEXPTIME, Inform. and control, 65, 158-181, (1985) · Zbl 0586.68042
[20] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[21] Kuich, W., Languages and enumeration of planted plane trees, Indag. math., 32, 268-280, (1970) · Zbl 0202.55901
[22] Kuich, W., A context-free language and enumeration problems in infinite trees and digraphs, J. combin. theory, 10, 135-142, (1971) · Zbl 0211.02001
[23] McKenzie, P.; Cook, S.A., The parallel complexity of abelian permutation group problems, Tech. rep. 181/85, (1985), Dept. of Computer Science, Univ. of Toronto
[24] Meyer, A.R.; Stockmeyer, L.J., Word problems requiring exponential time, Proc. 5th ACM symp. on theory of computing, 1-9, (1973) · Zbl 0359.68050
[25] Pippenger, N., On simultaneous resource bounds, Proc. 20th IEEE symp. on foundation of computer science, 307-311, (1979)
[26] Reif, J.H., Logarithmic depth circuits for algebraic functions, SIAM J. comput., 15, 231-242, (1986) · Zbl 0611.68014
[27] Ruzzo, W.L., On uniform circuit complexity, J. comput. system sci., 22, 365-383, (1981) · Zbl 0462.68013
[28] Salomaa, A.; Soittola, M., Automata theoretic aspects of formal power series, (1978), Springer New York · Zbl 0377.68039
[29] Schönhage, A.; Strassen, V., Schnelle multiplikation grosser zahlen, Computing, 7, 281-292, (1971) · Zbl 0223.68007
[30] Schützenberger, M.P., Certain elementary families of automata, Proc. symp. on mathematical theory of automata, 139-153, (1962)
[31] Schützenberger, M.P., Context-free languages and pushdown automata, Inform. and control, 6, 246-264, (1963) · Zbl 0123.12502
[32] Stockmeyer, L.J., The complexity of decision problems in automata theory and logic, Ph.D. thesis, (1974), MIT Project MAC TR-133
[33] Valiant, L.G., The complexity of computing the permanent, Theoret. comput. sci., 8, 189-202, (1979) · Zbl 0415.68008
[34] Valiant, L.G., The complexity of enumeration and reliability problems, SIAM J. comput., 8, 410-421, (1979) · Zbl 0419.68082
[35] Wagner, K.; Wechsung, G., Computational complexity, (1986), VEB Deutscher Verlag der Wissenschaften Berlin
[36] Wegener, I., The complexity of Boolean functions, (1987), Wiley New York and Teubner, Stuttgart · Zbl 0623.94018
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.