Proof Complexity and Textual Cohesion

Journal of Logic, Language and Information 24 (1):53-64 (2015)
  Copy   BIBTEX

Abstract

In the first section of this paper I define a set of measures for proof complexity, which combine measures in terms of length and space. In the second section these measures are generalized to the broader category of formal texts. In the third section of the paper I outline several applications of the proposed theory

Categories

Keywords

Reprint years

DOI

10.1007/s10849-014-9212-1

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,611

External links

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

Through your library

My notes

Similar books and articles

From syntactical to textual strategies of argumentation.Helmuth Feilke - 1996 - Argumentation 10 (2):197-212.
The Depth of Resolution Proofs.Alasdair Urquhart - 2011 - Studia Logica 99 (1-3):349-364.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Upper bounds on complexity of Frege proofs with limited use of certain schemata.Pavel Naumov - 2006 - Archive for Mathematical Logic 45 (4):431-446.
Deissler Rank Complexity of Powers of Indecomposable Injective Modules.R. Chartrand & T. Kucera - 1994 - Notre Dame Journal of Formal Logic 35 (3):398-402.
On meta complexity of propositional formulas and propositional proofs.Pavel Naumov - 2008 - Archive for Mathematical Logic 47 (1):35-52.
Forcing Complexity: Minimum Sizes of Forcing Conditions.Toshio Suzuki - 2001 - Notre Dame Journal of Formal Logic 42 (2):117-120.
Complexity and sustainability.Jennifer Wells - 2013 - New York: Routledge.
Proving properties of matrices over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{Z}_{2}}$$\end{document}. [REVIEW]Michael Soltys - 2012 - Archive for Mathematical Logic 51 (5-6):535-551.
Infinite Versions of Some Problems from Finite Complexity Theory.Jeffry L. Hirst & Steffen Lempp - 1996 - Notre Dame Journal of Formal Logic 37 (4):545-553.
Quantified propositional calculus and a second-order theory for NC1.Stephen Cook & Tsuyoshi Morioka - 2005 - Archive for Mathematical Logic 44 (6):711-749.
On the complexity of proof deskolemization.Matthias Baaz, Stefan Hetzl & Daniel Weller - 2012 - Journal of Symbolic Logic 77 (2):669-686.
Reasoning About Truth in First-Order Logic.Claes Strannegård, Fredrik Engström, Abdul Rahim Nizamani & Lance Rips - 2013 - Journal of Logic, Language and Information 22 (1):115-137.
Proof complexity of propositional default logic.Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas & Heribert Vollmer - 2011 - Archive for Mathematical Logic 50 (7-8):727-742.
Synthetic analysis: How science combats complexity.Sunny Auyang - manuscript

Analytics

Added to PP
2014-12-27

Downloads
21 (#743,384)

6 months
2 (#1,206,551)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Eli Dresner
Tel Aviv University

Citations of this work

No citations found.

Add more citations

References found in this work

Basic proof theory.A. S. Troelstra - 1996 - New York: Cambridge University Press. Edited by Helmut Schwichtenberg.

Add more references