Elementary linear logic revisited for polynomial time and an exponential time hierarchy extended versionReportar como inadecuado




Elementary linear logic revisited for polynomial time and an exponential time hierarchy extended version - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LIP - Laboratoire de l-Informatique du Parallélisme

Abstract : Elementary linear logic is a simple variant of linear logic, introduced by Girard and which characterizes in the proofs-as-programs approach the class of elementary functions computable in time bounded by a tower of exponentials of fixed height.
Our goal here is to show that despite its simplicity, elementary linear logic can nevertheless be used as a common framework to characterize the different levels of a hierarchy of deterministic time complexity classes, within elementary time.
We consider a variant of this logic with type fixpoints and weakening.
By selecting specific types we then characterize the class P of polynomial time predicates and more generally the hierarchy of classes k-EXP, for k>=0, where k-EXP is the union of DTIME2 k^{n^i}, for i>=1.


Keywords : linear logic implicit computational complexity proof-nets polynomial time lambda-calculus type systems





Autor: Patrick Baillot -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados