12 citations · 21 across the 7 of their papers we have counts for
10 papers
Continuous and monotone machines
Michal Konečný, Florian Steinberg, Holger Thies
We investigate a variant of the fuel-based approach to modeling diverging computation in type theories and use it to abstractly capture the essence of oracle Turing machines. The r…
Type-two Iteration with Bounded Query Revision
Bruce M. Kapron, Florian Steinberg
Motivated by recent results of Kapron and Steinberg (LICS 2018) we introduce new forms of iteration on length in the setting of applied lambda-calculi for higher-type poly-time com…
Computable analysis and notions of continuity in Coq
Florian Steinberg, Laurent Thery, Holger Thies
We give a number of formal proofs of theorems from the field of computable analysis. Many of our results specify executable algorithms that work on infinite inputs by means of oper…
Type-two polynomial-time and restricted lookahead
Bruce M. Kapron, Florian Steinberg
This paper provides an alternate characterization of type-two polynomial-time computability, with the goal of making second-order complexity theory more approachable. We rely on th…
Parametrised second-order complexity theory with applications to the study of interval computation
Eike Neumann, Florian Steinberg
We extend the framework for complexity of operators in analysis devised by Kawamura and Cook (2012) to allow for the treatment of a wider class of representations. The main novelty…
Polynomial running times for polynomial-time oracle machines
Akitoshi Kawamura, Florian Steinberg
This paper introduces a more restrictive notion of feasibility of functionals on Baire space than the established one from second-order complexity theory. Thereby making it possibl…
A minimal representation for continuous functions
Franz Brauße, Florian Steinberg
Kawamura and Cook specified the least set of information about a continuous function on the unit interval which is needed for fast function evaluation. This paper presents a variat…
Bounded time computation on metric spaces and Banach spaces
Matthias Schröder, Florian Steinberg
We extend the framework by Kawamura and Cook for investigating computational complexity for operators occurring in analysis. This model is based on second-order complexity theory f…
Complexity theory for spaces of integrable functions
Florian Steinberg
This paper investigates second-order representations in the sense of Kawamura and Cook for spaces of integrable functions that regularly show up in analysis. It builds upon prior w…
Comparing representations for function spaces in computable analysis
Arno Pauly, Florian Steinberg
This paper compares different representations (in the sense of computable analysis) of a number of function spaces that are of interest in analysis. In particular subspace represen…