# publications

preprints  books  journals  conferences  dissertations  tech.reports  reviews  editing

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

## preprints

 Total Search Problems in Bounded Arithmetic and Improved Witnessing, together with J-J Razafindrakoto. 17 pages, submitted. Cobham Recursive Set Functions and Weak Set Theories, together with S.R.Buss, S.-D. Friedman, M Müller and N Thapen. 50 pages, submitted.

## books

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

## publications in journals

 The NP Search Problems of Frege and Extended Frege Proofs, together with S.R.Buss. 24 pages, accepted. Deciding logics of linear Kripke frames with scattered end pieces, together with N. Preining. 9 pages, accepted in Soft Computing 2016. Cobham Recursive Set Functions, together with S.R.Buss, S.-D. Friedman, M Müller and N Thapen. APAL 2016, 167(3): 335-369 Safe Recursive Set Functions, together with S.R.Buss and S.-D. Friedman. JSL 2015, 80(3): 730-762. Separating intermediate predicate logics of well-founded and dually well-founded structures by monadic sentences, together with N. Preining. 21 pages. J Logic Computation (2015) 25(3): 527-547. Parity Games and Propositional Proofs, together with P. Pudlák and N. Thapen. 30 pages. ACM TOCL 2014, 15(2), 17:1-17:30. Improved Witnessing and Local Improvement Principles for Second-Order Bounded Arithmetic, together with S.R.Buss. 35 pages. ACM TOCL 2014, 15(1), 2:1-2:35. 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

 Hyper Natural Deduction, together with N Preining. LICS 2015 Parity Games and Propositional Proofs, together with P. Pudlák and N. Thapen. MFCS 2013 Using Domain Specific Languages to Support Verification in the Railway Domain, together with P. James and M. Roggenbach. HVC 2012 A Characterisation of Definable NP Search Problems in Peano Arithmetic, WoLLIC 2009 On the complexity of parity games, Visions of Computer Science 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 2017-03-30