Analytic cut trees
Logic Journal of the IGPL 8:733-750 (2000)
| Abstract | It has been maintained by Smullyan that the importance of cut-free proofs does not stem from cut elimination per se but rather from the fact that they satisfy the subformula property. In accordance with such a viewpoint in this paper we introduce <span class='Hi'>analytic</span> cut trees, a system from which cuts cannot be eliminated but satisfying the subformula property. Like tableaux <span class='Hi'>analytic</span> cut trees are a refutation system but unlike tableaux they have a single inference rule (a form of the <span class='Hi'>analytic</span> cut rule) and several branch closure rules. The main advantage of <span class='Hi'>analytic</span> cut trees over tableaux is efficiency: while <span class='Hi'>analytic</span> cut trees can simulate tableaux with an increase in complexity by at most a constant factor, tableaux cannot polynomially simulate <span class='Hi'>analytic</span> cut trees. Indeed <span class='Hi'>analytic</span> cut trees are intrinsically more efficient than any cut-free system. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,701 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesTang Yijie & Yan Xin (2008). The Contemporary Significance of Confucianism. Frontiers of Philosophy in China 3 (4):477 - 501.
Peter J. Taylor (1994). Shifting Frames: From Divided to Distributed Psychologies of Scientific Agents. PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1994:304 - 310.
H. M. Malm (1989). Commodification or Compensation: A Reply to Ketchum. Hypatia 4 (3):128 - 135.
J. L. Schellenberg (2005). The Hiddenness Argument Revisited (II). Religious Studies 41 (3):287 - 303.
P. X. Monaghan (2010). A Novel Interpretation of Plato's Theory of Forms. Metaphysica 11 (1):63-78.
H. E. Baber (1987). How Bad Is Rape? Hypatia 2 (2):125 - 138.
Katalin Bimbó (2007). $LE^{T}{Rightarrow}$ , $LR^{Circ}{Wedgesim}$ , LK and Cutfree Proofs. Journal of Philosophical Logic 36 (5):557 - 570.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads17 ( #71,134 of 549,124 )Recent downloads (6 months)3 ( #25,740 of 549,124 )How can I increase my downloads? |
My notes
Discussion
