Warning: Table './church/sessions' is marked as crashed and last (automatic?) repair failed query: SELECT sid FROM sessions WHERE sid = 'ivj0dghqahn93bbkhnec4h7fc1' in /var/www/church/includes/database.mysql.inc on line 121
Linear Logic and Polynomial Time | Gruppo di Logica e Geometria della Cognizione

Linear Logic and Polynomial Time

2006

Damiano Mazza

Mathematical Struactures in Computer Science 16 (6):947-988

Cambridge University Press

Abstract

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 the 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 normalization (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.

BibTeX


Warning: Can't find file: 'watchdog' (errno: 2) query: INSERT INTO watchdog (uid, type, message, severity, link, location, referer, hostname, timestamp) VALUES (0, 'php', 'Table './church/sessions' is marked as crashed and last (automatic?) repair failed\nquery: SELECT sid FROM sessions WHERE sid = 'ivj0dghqahn93bbkhnec4h7fc1' in /var/www/church/includes/database.mysql.inc on line 121.', 2, '', 'http://logica.uniroma3.it/node/136', '', '216.73.216.58', 1751747289) in /var/www/church/includes/database.mysql.inc on line 121