21 citations · 27 across the 6 of their papers we have counts for
4 papers · 1 filter
On the computational complexity of cut-reduction
Klaus Aehlig, Arnold Beckmann
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 sys…
A Finite Semantics of Simply-Typed Lambda Terms for Infinite Runs of<br> Automata
Klaus Aehlig
Model checking properties are often described by means of finite automata. Any particular such automaton divides the set of infinite trees into finitely many classes, according to…
An Elementary Fragment of Second-Order Lambda Calculus
Klaus Aehlig, Jan Johannsen
A fragment of second-order lambda calculus (System F) is defined that characterizes the elementary recursive functions. Type quantification is restricted to be non-interleaved and…
A syntactical analysis of non-size-increasing polynomial time computation
Klaus Aehlig, Helmut Schwichtenberg
A syntactical proof is given that all functions definable in a certain affine linear typed lambda-calculus with iteration in all types are polynomial time computable. The proof pro…