Cut and pay

Journal of Logic, Language and Information 15 (3):195-218 (2006)
  Copy   BIBTEX

Abstract

In this paper we study families of resource aware logics that explore resource restriction on rules; in particular, we study the use of controlled cut-rule and introduce three families of parameterised logics that arise from different ways of controlling the use of cut. We start with a formulation of classical logic in which cut is non-eliminable and then impose restrictions on the use of cut. Three Cut-and-Pay families of logics are presented, and it is shown that each family provides an approximation process for full propositional classical logic when the control over the use of cut is progressively weakened. A sound and complete semantics is given for each component of each of the three families of approximated logics. One of these families is shown to possess the uniform substitution property, a new result for approximated reasoning. A tableau based decision procedure is presented for each element of the approximation families and the complexity of each decision procedure is studied. We show that there are families in which every component logic can be decided polynomially.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,569

External links

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

Through your library

Similar books and articles

Analytics

Added to PP
2009-01-28

Downloads
64 (#184,490)

6 months
1 (#418,511)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Dov Gabbay
Hebrew University of Jerusalem

References found in this work

First-Order Logic.Raymond Merrill Smullyan - 1968 - Berlin, Germany: New York [Etc.]Springer-Verlag.
On the Theory of Inconsistent Formal Systems.Newton C. A. Costa - 1972 - Recife, Universidade Federal De Pernambuco, Instituto De Matemática.
On the Theory of Inconsistent Formal Systems.Newton C. A. da Costa - 1974 - Notre Dame Journal of Formal Logic 15 (4):497-510.

View all 13 references / Add more references