BIRS Workshop Lecture Videos
Algorithmic proof for the transcendence of D-finite power series Bostan, Alin
Given a sequence represented by a linear recurrence with polynomial coefficients and sufficiently many initial terms, a natural question is whether the transcendence of its generating function can be decided algorithmically. The question is non trivial even for sequences satisfying a recurrence of first order. An algorithm due to Michael Singer is sufficient, in principle, to answer the general case. However, this algorithm suffers from too high a complexity to be effective in practice. We will present a recent method that we have used to treat a non-trivial combinatorial example. It reduces the question of transcendence to a (structured) linear algebra problem.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International