[Prev][Next][Index][Thread]
Full affine logic is decidable
FULL PROPOSITIONAL AFFINE LOGIC IS DECIDABLE.
The full propositional Linear Logic is undecidable
(Lincoln, Mitchell, Scedrov, and Shankar). The decidability
problem for the full propositional Affine Logic LLW, i.e.
Linear Logic with the Weakening Rule, remained open.
Now, contrary to what might be expected, Alexey KOPYLOV
(a 3-d year undergraduate student under Artemov at Moscow University)
proved that the FULL propositional Affine Logic LLW is DECIDABLE.
His proof is based on
(a) reduction of full LLW (containing all the multiplicatives,
additives, exponentials, and constants) to sequents of specific
'normal forms', and
(b) a generalization of Kanovich's computational interpretation
of Linear Logic adapted to these 'normal forms'.
We have checked the proof, which was delivered in April of 1994.
The corresponding LaTeX paper is expected to be available soon via
ftp, we'll immediately let you know.
Best regards,
Artemov & Kanovich