  In this paper we obtain complexity bounds for computational problems on
algebraic power series over several commuting variables. The power series are
specified by systems of polynomial equations: a formalism closely related to
weighted context-free grammars. We focus on three problems -- decide whether a
given algebraic series is identically zero, determine whether all but finitely
many coefficients are zero, and compute the coefficient of a specific monomial.
We relate these questions to well-known computational problems on arithmetic
circuits and thereby show that all three problems lie in the counting
hierarchy. Our main result improves the best known complexity bound on deciding
zeroness of an algebraic series. This problem is known to lie in PSPACE by
reduction to the decision problem for the existential fragment of the theory of
real closed fields. Here we show that the problem lies in the counting
hierarchy by reduction to the problem of computing the degree of a polynomial
given by an arithmetic circuit. As a corollary we obtain new complexity bounds
on multiplicity equivalence of context-free grammars restricted to a bounded
language, language inclusion of a nondeterministic finite automaton in an
unambiguous context-free grammar, and language inclusion of a non-deterministic
context-free grammar in an unambiguous finite automaton.
