Komplexität und Programmiersprachen

Veranstalter

Prof. M. Hofmann, Dr. J. Johannsen

Zeit, Ort

Freitags 12–14 Uhr, Z1.09

Linear Logic, Proof Nets

• Girard. Linear Logic, 1987
• Girard. Linear Logic, its Syntax and Semantics, 1995
• Lafont. From Proof Nets to Interaction Nets, 1994

2. Juni – Ulrich Schöpp
Elementary Linear Logic

• Danos, Joinet. Linear Logic and Elementary Time, 1999

9. Juni – Klaus Aehlig
Light Affine Logic

• Asperti, Roversi. Light Affine Logic (Proof Nets, Programming Notation, P-Time Correctness and Completeness), 2004
• Terui. Light logic and polynomial time computation, PhD Thesis, 2002

23. Juni – Jan Johannsen
Dual Light Affine Logic

• Baillot, Terui. Light types for polynomial time computation in lambda-calculus, 2004
• Atassi, Baillot, Terui. Verification of Ptime reducibility for system F terms via Dual Light Affine Logic, 2006

30. Juni – Martin Hofmann
Bounded Linear Logic

• Hofmann, Scott. Realizability models for BLL-like languages, 2000

7. Juli – Stefan Schimanski
Soft Linear Logic

• Lafont. Soft linear logic and polynomial time, 2006

14. Juli – Andreas Abel
Rigorosum

21. Juli – Ulrich Schöpp
Komplexität der Schnittelimination für MLL, MLAL, MSLL, MLLL

• Mairson, Terui. On the Computational Complexity of Cut-Elimination in Linear Logic, 2003
• Mairson. MLL Normalization and Transitive Closure: Circuits, Complexity and Euler Tours, 2006
• Mairson. Linear lambda calculus and PTIME-completeness, 2003