F50-04: Algorithmic Lattice Path Counting Using the Kernel Method
The aim here is to develop computer algebra algorithms for solving functional equations via the kernel method, and to use them for classifying various kinds of lattice walks. The main question in the enumeration of restricted lattice walks is whether the generating function for a specific type of walk is D-finite or not. This question has been intensively studied during the past few years for walks restricted to the quarter plane, and as a result of this work, we now have not only a complete classification of these walks, but also a number of new techniques for checking whether a specific generating function is D-finite or not. Most of these techniques can be seen as variations and extensions of the classical kernel method for solving functional equations. Some of them are best-suited for hand-calculations, others depend heavily on computer algebra calculations, all have in common that they may fail to give a decision for the particular example at hand. The main goal of the proposed project part is to derive from the available techniques an algorithm which without any human interaction can decide for any given functional equation whether its solution is D-finite or not. Once such an algorithm is available, we want to use it to do automated classifications of new types of restricted lattice walks for which the number of different cases is so large that a classification by hand would be infeasible. We hope that the data obtained in these calculations will finally lead to a better understanding of the deeper reasons why certain generating functions are D-finite and others are not.