A representation theorem for (\(q\)-)holonomic sequences (Q386034)

The authors are interested in two families of sequences: holonomic sequences, i.e., sequences satisfying linear recurrence relations with polynomial coefficients, and their \(q\)-analogs, called \(q\)-holonomic sequences. More precisely, their purpose is to generalize the famous Chomsky-Schützenberger theorem, which implies that every sequence satisfying a linear recurrence relation with constant coefficients can be obtained as the difference of two counting functions of regular languages. The authors give representation theorems for both holonomic and \(q\)-holonomic sequences. Furthermore, they give a representation theorem for holonomic sequences that does not use regular but sparse regular languages.