Acyclicity and Coherence in Multiplicative and Exponential Linear Logic

09 / 2006

Michele Pagani

Computer Science Logic 4207:531-545

in Lecture Notes in Computer Science

Springer Berlin / Heidelberg

Abstract

We give a geometric condition that characterizes MELL proof structures whose interpretation is a clique in non-uniform coherent spaces: visible acyclicity. We define the visible paths and we prove that the proof structures which have no visible cycles are exactly those whose interpretation is a clique. It turns out that visible acyclicity has also nice computational properties, especially it is stable under cut reduction.

Download: vacCSL.pdf | vacCSL.ps

BibTeX