zbMATH — the first resource for mathematics

Linear logic and computation: A survey. (English) Zbl 0828.03004
Schwichtenberg, Helmut (ed.), Proof and computation. Proceedings of the NATO ASI summer school held in Marktoberdorf, Germany, July 20-August 1, 1993. Berlin: Springer-Verlag. NATO ASI Ser., Ser. F, Comput. Syst. Sci. 139, 379-395 (1995).
This is a survey of modeling various complexity classes (by a proof search) in fragments of linear logic. PSPACE-hardness of the nonmodal multiplicative additive linear logic is treated in some detail.
For the entire collection see [Zbl 0816.68017].
Reviewer: G.Mints (Stanford)

03B20 Subsystems of classical logic (including intuitionistic logic)
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDF BibTeX Cite