2026-04-17T11:49:45Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/1046712025-07-17T03:44:49Zcom_2072_1033col_2072_452950

00925njm 22002777a 4500 dc Cucker Farkas, Juan Felipe author Gabarró Vallès, Joaquim author 1989-12 Proves that nonprimitive recursive functions have transcendental generating series. This result translates a certain measure of the complexity of a function, the fact of not being primitive recursive, into another measure of the complexity of the generating series associated to the function, the fact of being transcendental. On démontre que les fonctions qui ne sont pas recursives primitives ont des séries génératrices transcendantes. Ce résultat traduit une certaine mesure de complexité d'une fonction, le fait de ne pas être recursive primitive, dans une autre mesure de la complexité de la série génératrice associée à cette fonction, le fait d'être transcendante. Postprint (published version) Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat Complexity, Computational Function complexity measures Nonrecursive functions Transcendental generating series Nonprimitive recursive functions Complexitat computacional Non recursive functions have transcendental generating functions