On the Computational Complexity of Cut-Reduction

June 24-June 27

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/LICS.2008.9

2008 23rd Annual IEEE Symposium on Lo ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Klaus Aehlig Articles by Arnold Beckmann

	ASCII Text	x
	Klaus Aehlig, Arnold Beckmann, "On the Computational Complexity of Cut-Reduction," Logic in Computer Science, Symposium on, pp. 284-293, 2008 23rd Annual IEEE Symposium on Logic in Computer Science, 2008.

	BibTex	x
	@article{ 10.1109/LICS.2008.9, author = {Klaus Aehlig and Arnold Beckmann}, title = {On the Computational Complexity of Cut-Reduction}, journal ={Logic in Computer Science, Symposium on}, volume = {0}, year = {2008}, issn = {1043-6871}, pages = {284-293}, doi = {http://doi.ieeecomputersociety.org/10.1109/LICS.2008.9}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Logic in Computer Science, Symposium on TI - On the Computational Complexity of Cut-Reduction SN - 1043-6871 SP284 EP293 A1 - Klaus Aehlig, A1 - Arnold Beckmann, PY - 2008 KW - cut-reduction KW - proof notations KW - propositional logic KW - Bounded Arithmetic VL - 0 JA - Logic in Computer Science, Symposium on ER -

Klaus Aehlig

Arnold Beckmann

Using appropriate notation systems for proofs, cut-reduction can often be rendered feasible on these notations. 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.

Index Terms:

cut-reduction, proof notations, propositional logic, Bounded Arithmetic

Citation:

Klaus Aehlig, Arnold Beckmann, "On the Computational Complexity of Cut-Reduction," lics, pp.284-293, 2008 23rd Annual IEEE Symposium on Logic in Computer Science, 2008

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.