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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00099077
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:50:47 AM
Last modification on : Wednesday, August 7, 2019 - 12:18:08 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

179