2 added 18 characters in body

Let $L$ be a language on a finite alphabet and let $L_n$ be the number of words of length $n$. Let $f_L(x) = \sum_{n \ge 0} L_n x^n$. The following are well-known:

• If $L$ is regular, then $f_L$ is rational.
• If $L$ is unambiguous and context-free, then $f_L$ is algebraic.

Does there exist a natural family of languages $\mathcal{L}$ containing the context-free languages such that if $L \in \mathcal{L}$, then $f_L$ is holonomic? Is that class of languages also associated to a natural class of automata?

This question is prompted by a remark in Flajolet and Sedgewick where they assert that there is no meaningful generating function formalism associated to context-sensitive languages because of the significant undecidability issues. However, holonomic functions have proven a robust and incredibly useful framework in combinatorics, so I think this is a natural question to ask.

1

# Is there a natural family of languages whose generating functions are holonomic (i.e. D-finite)?

Let $L$ be a language on a finite alphabet and let $L_n$ be the number of words of length $n$. Let $f_L(x) = \sum_{n \ge 0} L_n x^n$. The following are well-known:

• If $L$ is regular, then $f_L$ is rational.
• If $L$ is context-free, then $f_L$ is algebraic.

Does there exist a natural family of languages $\mathcal{L}$ containing the context-free languages such that if $L \in \mathcal{L}$, then $f_L$ is holonomic? Is that class of languages also associated to a natural class of automata?

This question is prompted by a remark in Flajolet and Sedgewick where they assert that there is no meaningful generating function formalism associated to context-sensitive languages because of the significant undecidability issues. However, holonomic functions have proven a robust and incredibly useful framework in combinatorics, so I think this is a natural question to ask.