Holonomic generating functions and context free languages. (English) Zbl 0754.68064

Bertoni, A.; Massazza, P.; Sabadini, N.

Int. J. Found. Comput. Sci. 3, No. 2, 181-191 (1992).

Summary: 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 \(LCL_ R\).

MSC:

68Q45	Formal languages and automata
05A15	Exact enumeration problems, generating functions

Keywords:

Turing equivalence; differential equations; decidability; holonomic generating function