The complexity of decision procedures in relevance logic II
- 1 December 1999
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 64 (4) , 1774-1802
Abstract
In this paper, we show that there is no primitive recursive decision procedure for the implication-conjunction fragments of the relevant logics R, E and T, as well as for a family of related logics. The lower bound on the complexity is proved by combining the techniques of an earlier paper on the same subject [20] with a method used by Lincoln, Mitchell, Scedrov and Shankar in proving that propositional linear logic is undecidable.The decision problem for the pure implicational fragments of E and R were solved by Saul Kripke in a tour de force of combinatorial reasoning, published only as an abstract [9]. Belnap and Wallace extended Kripke's decision procedure to the implication-negation fragment of E in [3]; an account of their decision method is to be found in [1, pp. 124–139]. The decision method extends immediately to the implication/negation fragment of R. In fact, in the case of R we can go farther: Meyer in his thesis [13] showed how to translate the logic LR, which results from R by omitting the distribution axiom, into R→⋀, so that the decision procedure can be extended to all of LR. This decision procedure has been implemented as a program Kripke by Thistlewaite, McRobbie and Meyer [17]. The program is not simply a straightforward implementation of the decision procedure; finite matrices are used extensively to prune invalid nodes from the search tree.Keywords
This publication has 9 references indexed in Scilit:
- Decision problems for propositional linear logicAnnals of Pure and Applied Logic, 1992
- The Complexity of Decision Procedures in Relevance Logic1990
- Petri nets and large finite setsTheoretical Computer Science, 1984
- The Complexity of the Finite Containment Problem for Petri NetsJournal of the ACM, 1981
- Parallel program schemataJournal of Computer and System Sciences, 1969
- Counter machines and counter languagesTheory of Computing Systems, 1968
- A Decision Procedure For the System EĪ of Entailment with NegationMathematical Logic Quarterly, 1965
- Ordering by Divisibility in Abstract AlgebrasProceedings of the London Mathematical Society, 1952
- Finiteness of the Odd Perfect and Primitive Abundant Numbers with n Distinct Prime FactorsAmerican Journal of Mathematics, 1913