A representation theorem for (q-)holonomic sequences

• We prove representation theorems for sequences with recurrence relations.
• (q-)Holonomic sequences are captured by appropriate logical interpretations.
• Representations based on positional weights of words in regular languages are shown.
• A weightless sparse-structures representation is given for holonomic sequences only.

Chomsky and Schützenberger showed in 1963 that the sequence dL(n)dL(n), which counts the number of words of a given length n in a regular language L, satisfies a linear recurrence relation with constant coefficients for n  , i.e., it is C-finite. It follows that every sequence s(n)s(n) which satisfies a linear recurrence relation with constant coefficients can be represented as dL1(n)−dL2(n)dL1(n)−dL2(n) for two regular languages. We view this as a representation theorem for C-finite sequences. Holonomic or P-recursive sequences are sequences which satisfy a linear recurrence relation with polynomial coefficients. q-Holonomic sequences are the q-analog of holonomic sequences. In this paper we prove representation theorems of holonomic and q-holonomic sequences based on position specific weights on words, and for holonomic sequences, without using weights, based on sparse regular languages.