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

Daniel Leivant 1 Jean-Yves Marion 2
2 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Type de document :
Article dans une revue
Information and Computation, Elsevier, 2000, 12 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00099077
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:50:47
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00099077, version 1

Collections

Citation

Daniel Leivant, Jean-Yves Marion. Ramified Recurrence and Computational Complexity IV : Predicative Functionals and Poly-Space. Information and Computation, Elsevier, 2000, 12 p. 〈inria-00099077〉

Partager

Métriques

Consultations de la notice

136