Ramified Recurrence and Computational Complexity IV : Predicative Functionals and Poly-Space - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Information and Computation Année : 2000

Ramified Recurrence and Computational Complexity IV : Predicative Functionals and Poly-Space

Résumé

We formulate a notion of predicative function types, and define predicative recurrence over functions, both in equational style and as an applicative formalism, pointing out the equivalence between the two approaches. We then show that a function is polyspace iff it is defined using predicative functionals obtained by ramified recurrence over words.
Fichier non déposé

Dates et versions

inria-00099077 , version 1 (26-09-2006)

Identifiants

  • HAL Id : inria-00099077 , version 1

Citer

Daniel Leivant, Jean-Yves Marion. Ramified Recurrence and Computational Complexity IV : Predicative Functionals and Poly-Space. Information and Computation, 2000, 12 p. ⟨inria-00099077⟩
120 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More