Mostrar el registro sencillo del ítem

Ponencia

dc.creatorCordón Franco, Andréses
dc.creatorFernández Margarit, Alejandroes
dc.creatorLara Martín, Francisco Félixes
dc.date.accessioned2019-06-28T08:19:49Z
dc.date.available2019-06-28T08:19:49Z
dc.date.issued2004
dc.identifier.citationCordón Franco, A., Fernández Margarit, A. y Lara Martín, F.F. (2004). Provably Total Primitive Recursive Functions: Theories with Induction. En CSL 2004: 18th International Workshop on Computer Science Logic (355-369), Karpacz, Poland: Springer.
dc.identifier.isbn978-3-540-23024-3es
dc.identifier.issn0302-9743es
dc.identifier.urihttps://hdl.handle.net/11441/87666
dc.description.abstractA natural example of a function algebra is R (T), the class of provably total computable functions (p.t.c.f.) of a theory T in the language of first order Arithmetic. In this paper a simple characterization of that kind of function algebras is obtained. This provides a useful tool for studying the class of primitive recursive functions in R (T). We prove that this is the class of p.t.c.f. of the theory axiomatized by the induction scheme restricted to (parameter free) Δ1(T)–formulas (i.e. Σ1–formulas which are equivalent in T to Π1–formulas). Moreover, if T is a sound theory and proves that exponentiation is a total function, we characterize the class of primitive recursive functions in R (T) as a function algebra described in terms of bounded recursion (and composition). Extensions of this result are related to open problems on complexity classes. We also discuss an application to the problem on the equivalence between (parameter free) Σ1–collection and (uniform) Δ1–induction schemes in Arithmetic. The proofs lean upon axiomatization and conservativeness properties of the scheme of Δ1(T)–induction and its parameter free version.es
dc.formatapplication/pdfes
dc.language.isoenges
dc.publisherSpringeres
dc.relation.ispartofCSL 2004: 18th International Workshop on Computer Science Logic (2004), p 355-369
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.titleProvably Total Primitive Recursive Functions: Theories with Inductiones
dc.typeinfo:eu-repo/semantics/conferenceObjectes
dcterms.identifierhttps://ror.org/03yxnpp24
dc.type.versioninfo:eu-repo/semantics/submittedVersiones
dc.rights.accessRightsinfo:eu-repo/semantics/openAccesses
dc.contributor.affiliationUniversidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificiales
dc.relation.publisherversionhttps://link.springer.com/chapter/10.1007%2F978-3-540-30124-0_28es
dc.identifier.doi10.1007/978-3-540-30124-0_28es
idus.format.extent15es
dc.publication.initialPage355es
dc.publication.endPage369es
dc.eventtitleCSL 2004: 18th International Workshop on Computer Science Logices
dc.eventinstitutionKarpacz, Polandes
dc.relation.publicationplaceBerlines
dc.identifier.sisius6530497es

FicherosTamañoFormatoVerDescripción
Provably Total Primitive.pdf342.1KbIcon   [PDF] Ver/Abrir  

Este registro aparece en las siguientes colecciones

Mostrar el registro sencillo del ítem

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Excepto si se señala otra cosa, la licencia del ítem se describe como: Attribution-NonCommercial-NoDerivatives 4.0 Internacional