2026-04-17T03:41:42Zhttps://recercat.cat/oai/request

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

urn:hdl:2117/104671 Non recursive functions have transcendental generating functions Cucker Farkas, Juan Felipe Gabarró Vallès, Joaquim À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 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) 1989-12 Article http://archive.numdam.org/article/ITA_1989__23_4_445_0.pdf Open Access