dc.contributor
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor
Facultat d'Informàtica de Barcelona
dc.contributor
Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
dc.contributor.author
Cucker Farkas, Juan Felipe
dc.contributor.author
Gabarró Vallès, Joaquim
dc.identifier
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.
dc.identifier
https://hdl.handle.net/2117/104671
dc.description.abstract
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.
dc.description.abstract
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.
dc.description.abstract
Postprint (published version)
dc.format
application/pdf
dc.relation
http://archive.numdam.org/article/ITA_1989__23_4_445_0.pdf
dc.subject
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
dc.subject
Complexity, Computational
dc.subject
Function complexity measures
dc.subject
Nonrecursive functions
dc.subject
Transcendental generating series
dc.subject
Nonprimitive recursive functions
dc.subject
Complexitat computacional
dc.title
Non recursive functions have transcendental generating functions
