Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-29T03:54:53.319Z Has data issue: false hasContentIssue false
  • English
  • Français

The complexity of decision procedures in relevance logic II

Published online by Cambridge University Press:  12 March 2014

Alasdair Urquhart
Alasdair Urquhart*
Affiliation:
Department of Philosophy, University of Toronto, 215 Huron Street, Toronto, Ontario, Canada, M5S 1A1, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 64 , Issue 4 , December 1999 , pp. 1774 - 1802
Copyright
Copyright © Association for Symbolic Logic 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Anderson, A. R. and Belnap, N. D. Jr., Entailment, vol. 1, Princeton University Press, Princeton, NJ, 1975.Google Scholar
[2]Anderson, A. R., Belnap, N. D. Jr., and Dunn, J. M., Entailment, vol. 2, Princeton University Press, Princeton, NJ, 1992.Google Scholar
[3]Belnap, N.D. Jr. and Wallace, J.R., A decision procedure for the system Eī of entailment with negation, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 11 (1965), pp. 277–289.CrossRefGoogle Scholar
[4]Dickson, L.E., Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors, American Journal of Mathematics, vol. 35 (1913), pp. 413–422.CrossRefGoogle Scholar
[5]Fischer, P.C., Meyer, A.R., and Rosenberg, A.L., Counter machines and counter languages, Mathematical Systems Theory, vol. 2 (1968), pp. 265–283.CrossRefGoogle Scholar
[6]Higman, G., Ordering by divisibility in abstract algebras, Proceedings of the London Mathematical Society, vol. 2 (1952), pp. 326–336.CrossRefGoogle Scholar
[7]Hopcroft, John E. and Ullman, Jeffrey D., Introduction to automata theory, languages and computation, Addison-Wesley, 1979.Google Scholar
[8]Karp, R.M. and Miller, R.E., Parallel program schemata, Journal of Computer and System Sciences, vol. 3 (1969), pp. 147–195.CrossRefGoogle Scholar
[9]Kripke, Saul A., The problem of entailment, this Journal, vol. 24 (1959), p. 324, Abstract.Google Scholar
[10]Lincoln, P., Mitchell, J., Scedrov, A., and Shankar, N., Decision problems for propositional linear logic, Annals of Pure and Applied Logic, vol. 56 (1992), pp. 239–311.CrossRefGoogle Scholar
[11]Mayr, Ernst W. and Meyer, Albert R., The complexity of the finite containment problem for Petri nets, Journal of the Association for Computing Machinery, vol. 28 (1981), pp. 561–576.CrossRefGoogle Scholar
[12]McAloon, Kenneth, Petri nets and large finite sets, Theoretical Computer Science, vol. 32 (1984), pp. 173–183.CrossRefGoogle Scholar
[13]Meyer, R.K., Topics in modal and many-valued logic, Ph.D. thesis, University of Pittsburgh, Pennsylvania, 1966.Google Scholar
[14]Meyer, R.K. and Giambrone, S., R+ is contained in T+, Bulletin of the Section of Logic, Polish Academy of Sciences, vol. 9 (1980), pp. 30–32.Google Scholar
[15]Rose, H.E., Subrecursion: functions and hierarchies, Oxford University Press, Oxford, 1984, Oxford Logic Guides 9.Google Scholar
[16]Simpson, Stephen G., Ordinal numbers and the Hilbert basis theorem, this Journal, vol. 53 (1988), pp. 961–974.Google Scholar
[17]Thistlewaite, P.B., McRobbie, M.A., and Meyer, R.K., Automated theorem-proving in nonclassical logics, Pitman, London, 1988.Google Scholar
[18]Troelstra, Anne S., Lectures on linear logic, CSLI, Menlo Park, California, 1992, CSLI Lecture Notes Number 29.Google Scholar
[19]Urquhart, Alasdair, The undecidability of entailment and relevant implication, this Journal, vol. 49 (1984), pp. 1059–1073.Google Scholar
[20]Urquhart, Alasdair, The complexity of decision procedures in relevance logic, Truth or consequences: Essays in honour of Nuel Belnap (Dunn, J. Michael and Gupta, Anil, editors), Kluwer, Dordrecht, 1990, pp. 61–76.CrossRefGoogle Scholar