A PSPACE-complete fragment of second-order linear logic - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 1999

A PSPACE-complete fragment of second-order linear logic

Résumé

Existentially quantified variables are the source of non decidability for second order linear logic without exponentials (MALL2). We present a decision procedure for a fragment of MALL2 based on a canonical instantiation of these variables and using inference permutability in proofs. We also establish that this fragment is PSPACE-complete.

Domaines

Autre [cs.OH]

Dates et versions

inria-00098816 , version 1 (26-09-2006)

Identifiants

Citer

Guy Perrier. A PSPACE-complete fragment of second-order linear logic. Theoretical Computer Science, 1999, 224 (1-2), pp.267-289. ⟨10.1016/S0304-3975(98)00315-6⟩. ⟨inria-00098816⟩
77 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More