A Representation Theorem for Holonomic Sequences Based on Counting Lattice Paths

Issue title: Lattice Path Combinatorics and Applications

Article type: Research Article

Authors: Kotek, Tomer | Makowsky, Johann A.

Affiliations: Department of Computer Science, Technion–Israel Institute of Technology, 32000 Haifa, Israel, {tkotek,janos}@cs.technion.ac.il

Note: [] Partially supported by a grant of the Graduate School of the Technion–Israel Institute of Technology

Note: [] Partially supported by a grant of the Fund for Promotion of Research of the Technion–Israel Institute of Technology and grant ISF 1392/07 of the Israel Science Foundation (2007-2011) Address for correspondence: Department of Computer Science, Technion–Israel Institute of Technology, 32000 Haifa, Israel

Abstract: Using a theorem of N. Chomsky and M. Schützenberger one can characterize sequences of integers which satisfy linear recurrence relations with constant coefficients (C-finite sequences) as differences of two sequences counting words in regular languages. We prove an analog for P-recursive (holonomic) sequences in terms of counting certain lattice paths.

DOI: 10.3233/FI-2012-696

Journal: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 199-213, 2012