Equality and zeroness problems of power series for combinatorial enumeration

Prelegent(ci)

Lorenzo Clemente

Afiliacja

MIM UW

Termin

19 kwietnia 2023 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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 series and find a natural application as exponential generating functions in combinatorial enumeration (read: combinatorial species by André Joyal). For instance, the exponential generating functions of Bell numbers B(n), of Cayley trees (sequence n^(n-1)), of series-parallel graphs, and of languages of unordered trees defined by Presburger tree automata are CDF. Bergeron & Reutenauer observed that the zeroness / equality problem for univariate 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 2-EXP length. (This is significant since in the discrete counterpart of polynomial recursive sequences no such elementary bound is known.) We extend this result in two directions. First, we show that the 2-EXPTIME complexity is retained for multivariate CDF. (This is worthy of note since in the discrete non-commutative counterpart of polynomial automata zeroness is Ackermann-hard.) Second, we show that the problem is in PTIME for CDF satisfying a system of linear differential equations, improving on the 1-EXP bound given by [Novikov & Yakovenko 1999]. Along the way, we show that multivariate CDF is a very robust class with many pleasant closure properties.

---