Title :
Decision problems for propositional linear logic
Author :
Lincoln, Patrick ; Michell, J. ; Scedrov, Andre ; Shankar, Natarajan
Author_Institution :
Dept. of Comput. Sci., Stanford Univ., CA, USA
Abstract :
It is shown that, unlike most other propositional (quantifier-free) logics, full propositional linear logic is undecidable. Further, it is provided that without the model storage operator, which indicates unboundedness of resources, the decision problem becomes PSPACE-complete. Also established are membership in NP for the multiplicative fragment, NP-completeness for the multiplicative fragment extended with unrestricted weakening, and undecidability for certain fragments of noncommutative propositional linear logic
Keywords :
decidability; formal logic; NP-completeness; PSPACE-complete; decision problem; multiplicative fragment; noncommutative propositional linear logic; propositional linear logic; undecidability; unrestricted weakening; Calculus; Computer science; Laboratories; Linear systems; Logic; Mathematics; Resource management; Scholarships;
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
DOI :
10.1109/FSCS.1990.89588
