Complexity of deciding equality of power series from combinatorial enumeration

A power series is constructible differentially finite (CDF) if it satisfies a system of polynomial differential equations [Bergeron & Reutenauer 1990, Bergeron & Sattler 1995]. CDF series generalise algebraic power se- ries and find a natural application as exponential generating functions in combinatorial enumeration (e. g. , combinatorial species by Andre Joyal). For instance, the exponential generating functions of Bell numbers B(n), of rooted Cayley trees (sequence nn−1), of series-parallel graphs, and of languages of unordered trees defined by Parikh tree automata are CDF. Bergeron & Reutenauer observed that the equality problem for univari- ate CDF series is decidable, without providing a complexity bound. We show that zeroness of univariate CDF series can be solved in elementary (2-EXPTIME) complexity. The proof relies on a technical lemma from [Novikov & Yakovenko 1999] showing that chains of polynomial ideals generated by iterated Lie derivatives have at most doubly exponential length. We then extend this result in two directions. First, we show that the 2-EXPTIME complexity is retained for multivariate CDF. Second, we show that the problem is in PTIME for CDF satisfying a system of linear differential equations with constant coefficients. Along the way, we show that multivariate CDF is a very robust class with many pleasant closure properties. Contributed talk given by Lorenzo Clemente

Authors

• Lorenzo Clemente

Keywords

No keywords are indexed for this paper.