Zeroness of weighted commutative grammars and combinatorial enumeration

We study weighted commutative grammars, a generalisation of Schützenberger's weighted finite automata inspired from process algebra and Petri net theory. Weighted grammars recognise a class of formal series Σ* → ℚ which we call *shuffle finite*. Our main result is that equivalence and zeroness of shuffle-finite series can be decided in 2-EXPSPACE. We find this remarkable since other weighted nonlinear models (e.g., polynomial automata) have a provably non-elementary complexity.

We then discuss two applications of this result. In the first application, we show that the multiplicity equivalence problem for commutative grammars is decidable, with the same complexity. The same problem for (ordinary) grammars has been open for a long time.
In the second application, we investigate the subclass of *commutative* shuffle-finite series (the output does not depend on the order of input symbols). In fact, this class was already studied in the 1990's by Bergeron and Reutenauer under the name of CDA power series. This is a large class of multivariate differentially algebraic power series well-suited to model counting problems in combinatorial enumeration, however decidability of equality has been open so far. We apply our decision procedure to obtain a 2-EXPTIME algorithm for the equality problem for CDA power series. In turn, this yields a procedure to decide equivalence of counting problems for a large class of recursively defined finite structures (including lists, trees, series-parallel graphs, etc...).