Chomsky and Schützenberger showed in 1963 that the sequence $d_L(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$. Kotek and Makowsky (2009) showed that every sequence $s(n)$ which satisfies a linear recurrence relation with constant coefficients can be represented as $d_{L_1}(n)- d_{L_2}(n)$ for two regular languages. Holonomic or P-recursive sequences are sequences which satisfy a linear recurrence relation with polynomial coefficients. E. Specker (1988) asked whether there is a similar characterization of holonomic sequences. In this talk we introduce the notion of logical interpretations of sequences of integers using Monadic Second Order Logic MSOL (MSOL-interpretations), and give two characterizations of holonomic sequences via MSOL-interpretations.