HOLONOMIC GENERATING FUNCTIONS AND CONTEXT FREE LANGUAGES
Alberto Bertoni, Paolo Massazza, Nicoletta Sabadini · International Journal of Foundations of Computer Science · 1992
In this paper we give some undecidability and decidability results about context-free languages. First, we prove that the problem of deciding whether a context-free language which admits a holonomic generating function is Turing equivalent to the finiteness question for r.e. sets. Second, we show that the Equivalence Problem is decidable for a suitable class of languages, called LCLR.