Linear logic and polynomial time

• Autores: Damiano Mazza
• Localización: Mathematical structures in computer science, ISSN 0960-1295, Vol. 16, Nº 6, 2006, págs. 947-988
• Idioma: inglés
• DOI: 10.1017/s0960129506005688
• Texto completo no disponible (Saber más ...)
• Resumen

  • Light and Elementary Linear Logic, which form key components of the interface between logic and implicit computational complexity, were originally introduced by Girard as ¿stand-alone¿ logical systems with a (somewhat awkward) sequent calculus of their own. The latter was later reformulated by Danos and Joinet as a proper subsystem of linear logic, whose proofs satisfy a certain structural condition. We extend this approach to polytime computation, finding two solutions: the first is obtained by a simple extension of Danos and Joinet's condition, closely resembles Asperti's Light Affine Logic and enjoys polystep strong normalisation (the polynomial bound does not depend on the reduction strategy); the second, which needs more complex conditions, exactly corresponds to Girard's Light Linear Logic.