The complexity of computing the number of strings of given length in context-free languages (Q1178713)

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).