Conference Paper/Proceeding/Abstract 1722 views
On the Computational Complexity of Cut-Reduction
Klaus Aehlig,
Arnold Beckmann 
Pages: 284 - 293
Swansea University Author:
Arnold Beckmann
Full text not available from this repository: check for access using links below.
DOI (Published version): 10.1109/LICS.2008.9
Abstract
Using appropriate notation systems for proofs, cut-reduction can often be rendered feasible on these notations, and explicit bounds can be given. Developing a suitable notation system for Bounded Arithmetic, and applying these bounds, all the known results on definable functions of certain such theo...
| ISSN: | 1043-6871 |
|---|---|
| Published: |
IEEE
2008
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa57 |
| Abstract: |
Using appropriate notation systems for proofs, cut-reduction can often be rendered feasible on these notations, and explicit bounds can be given. Developing a suitable notation system for Bounded Arithmetic, and applying these bounds, all the known results on definable functions of certain such theories can be reobtained in a uniform way. |
|---|---|
| Item Description: |
In 23rd Annual IEEE Symposium on Logic in Computer Science, Proceedings, Pittsburgh, PA, USA |
| College: |
Faculty of Science and Engineering |
| Start Page: |
284 |
| End Page: |
293 |