2026-04-14T03:44:54Zhttps://recercat.cat/oai/request

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

Non recursive functions have transcendental generating functions Cucker Farkas, Juan Felipe Gabarró Vallès, Joaquim Universitat Politècnica de Catalunya. Departament de Ciències de la Computació Facultat d'Informàtica de Barcelona Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals À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 Cucker, J., Gabarro, J. Non recursive functions have transcendental generating functions. "RAIRO. Theoretical informatics and applications", Desembre 1989, vol. 23, núm. 4, p. 445-448. 0988-3754 https://hdl.handle.net/2117/104671 eng http://archive.numdam.org/article/ITA_1989__23_4_445_0.pdf Open Access 4 p. application/pdf