Light Logics for Polynomial Time Computations April 3th
58 pages
English

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Light Logics for Polynomial Time Computations April 3th

-

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
58 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Niveau: Supérieur
Light Logics for Polynomial Time Computations April 3th 2012 – 1 / 33 Light Logics for Polynomial Time Computations Marco Gaboardi University of Pennsylvania Università di Bologna Inria Focus Team

  • predicative recursion

  • explicit cost

  • machine model

  • light logics

  • pr functions over


Sujets

Informations

Publié par
Nombre de lectures 6
Langue English
Poids de l'ouvrage 15 Mo

Extrait

Light Logics for Polynomial Time Computations
Marco Gaboardi University of Pennsylvania Università di Bologna Inria Focus Team
LightLogicsforPolynomialTimeComputations
April 3th 2012 – 1 / 33
01h22/2–33
FPTIME  Boundedness StratiÞcation
Computation
Implicit Computational Complexity
ltniuOforPgicshtLoeLigmoCemiTlaimonylo3tilprsAontitapu
Implicit Computational Complexity
LightLogicsforPolynomialTimeComputations
April 3th 2012 – 3 / 33
Implicit Computational Complexity: Motivations
ICCaims at describingcomplexity classeswithout:
– –
explicit reference to a speciÞc machine model without an explicit cost bound
LightLogicsforPolynomialTimeComputations
April 3th 2012 – 4 / 33
Implicit Computational Complexity: Motivations
ICCaims at describingcomplexity classeswithout: –explicit reference to a speciÞc machine model –without an explicit cost bound ItgenerallyborrowstechniquesfromMathematicalLogic: –Recursion Theory, FPTIME = Predicative Recursion on Notation –Structural Proof Theory,FPTIME = Bounded/Light Linear Logic –Model Theory, FPTIME = PR Functions over Finite Structures
LightLogicsforPolynomialTimeComputations
April 3th 2012 – 4 / 33
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents