arnold beckmann's pages

publications

Warning! The online versions presented here may differ from the actual published versions!

preprints

	Safe Recursive Set Functions,
	together with S.R.Buss and S.-D. Friedman. 26 pages.
	Improved Witnessing and Local Improvement Principles for Second-Order Bounded Arithmetic,
	together with S.R.Buss. 45 pages.

books

	Bounded Arithmetic and Resolution-Based Proof Systems,
	Collegium Logicum Vol. 7, 2004, together with J. Johannsen.

publications in journals

	Corrected Upper Bounds for Free-Cut Elimination,
	together with S.R.Buss. TCS 2011, 412(39): 5433-5445.
	Characterising Definable Search Problems in Bounded Arithmetic via Proof Notations,
	together with S.R.Buss. In: Ways of Proof Theory, ed. R. Schindler, Ontos Series on Mathematical Logic, pp. 65-134, 2010.
	On the computational complexity of cut-reduction,
	together with K.T.Aehlig. Ann.Pure.Appl.Logic 2010, 161: 711-736.
	Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic,
	together with S.R.Buss. Journal of Mathematical Logic 2009, 9(1): 103-138.
	Continuous Fraisse Conjecture,
	together with M. Goldstern and N. Preining. Order 2008, 25: 281-298.
	Linear Kripke Frames and Gödel Logics,
	together with N. Preining. JSL 2007, 72(1): 26-44.
	Generalised dynamic ordinals - universal measures for implicit computational complexity,
	Logic Colloquium '02, LNL, 27, Assoc. Symb. Logic, La Jolla, CA, 2006, pp. 48 - 74.
	Uniform proof complexity,
	Journal of Logic and Computation 2005, 15: 433-446.
	Separation results for the size of constant-depth propositional proofs,
	Ann.Pure.Appl.Logic 2005, 136: 30-55, together with S. Buss.
	An Unexpected Separation Result in Linearly Bounded Arithmetic,
	Math. Log. Quart. 2005, 51: 191-200, together with J. Johannsen.
	Preservation theorems and restricted consistency statements in bounded arithmetic,
	Ann.Pure.Appl.Logic 2004, 126: 255-280
	Dynamic ordinal analysis,
	Arch. Math. Logic 2003, 42: 303-334.
	Ordinal Notations and Well-Orderings in Bounded Arithmetic,
	Ann.Pure.Appl.Logic 2003, 120: 197-223, together with S. Buss and C. Pollett
	Notations for Exponentiation,
	TCS 2002, 288(1): 3-19.
	Proving consistency of equational theories in bounded arithmetic,
	JSL 2002, 67(1): 279-296.
	A non-well-founded primitive recursive tree, provably well-founded for co-r.e. sets,
	Arch.Math.Logic 2002, 41(3): 251-257.
	Exact bounds for lengths of reductions in typed $\lambda$-calculus,
	JSL 2001, 66(3): 1277-1285.
	Analyzing Gödel's T via expanded head reduction trees,
	Math.Log.Quat. 2000, 46(4): 517-536, together with A. Weiermann.
	Characterizing the elementary recursive functions by a fragment of Gödel's T.,
	Arch.Math.Logic 2000, 39: 475-491, together with A. Weiermann
	Applications of cut-free infinitary derivations to generalized recursion theory,
	Ann.Pure.Appl.Logic 1998, 94: 7-19, together with W. Pohlers.
	A term rewriting characterization of the polytime functions and related complexity classes,
	Arch. Math. Logic 1996, 36: 11-30, together with A. Weiermann.

publications at conferences

	A Characterisation of Definable NP Search Problems in Peano Arithmetic,
	WoLLIC 2009
	On the complexity of parity games,
	2008, together with F. G. Moller.
	On the computational complexity of cut-reduction,
	LICS 2008, together with K.T.Aehlig.
	Propositional Logic for Circuit Classes,
	together with K.T.Aehlig, CSL 2007.
	A note on universal measures for weak implicit computational complexity,
	LPAR 2002.
	Resolution Refutations and Propositional Proofs with Height-Restrictions,
	CSL 2002.

technical reports

	Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic,
	2008, together with S.R.Buss, Swansea University Computer Science technical report CSR15-2008.
	On the computational complexity of cut-reduction,
	together with K.T.Aehlig, Swansea University Computer Science technical report CSR15-2007.
	Height restricted constant depth LK,
	ECCC Report TR03-034, 2003.

dissertations

	Separating fragments of bounded arithmetic,
	PhD-thesis, 1996.
	Beschränkte Arithmetik in scharf beschränkten Theorien zweiter Stufe,
	Diplomarbeit, 1992.

reviews

	Review on two papers of Takeuti,
	BSL, 2002.

websites: Arnold Beckmann

2012-05-15