The contraction rule and decision problems for logics without structural rules

Studia Logica 50 (2):299 - 319 (1991)

Abstract

This paper shows a role of the contraction rule in decision problems for the logics weaker than the intuitionistic logic that are obtained by deleting some or all of structural rules. It is well-known that for such a predicate logic L, if L does not have the contraction rule then it is decidable. In this paper, it will be shown first that the predicate logic FLec with the contraction and exchange rules, but without the weakening rule, is undecidable while the propositional fragment of FLec is decidable. On the other hand, it will be remarked that logics without the contraction rule are still decidable, if our language contains function symbols.

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,766

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2009-01-28

Downloads
36 (#320,472)

6 months
1 (#386,989)

Historical graph of downloads
How can I increase my downloads?

References found in this work

A Completeness Theorem in Modal Logic.Saul A. Kripke - 1959 - Journal of Symbolic Logic 24 (1):1-14.
A Decision Procedure For the SystemEĪ of Entailment with Negation.Nuel D. Belnap & John R. Wallace - 1965 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 11 (4):277-289.
Predicate Logics Without the Structure Rules.Yuichi Komori - 1986 - Studia Logica 45 (4):393 - 404.

View all 6 references / Add more references

Citations of this work

Proof Theory and Algebra in Logic.Hiroakira Ono - 2019 - Singapore: Springer Singapore.
Interpolation Via Translations.João Rasga, Walter Carnielli & Cristina Sernadas - 2009 - Mathematical Logic Quarterly 55 (5):515-534.

View all 7 citations / Add more citations

Similar books and articles