31 citations · 92 across the 14 of their papers we have counts for
5 papers · 1 filter
Ramified Structural Recursion and Corecursion
Norman Danner, James S. Royer
We investigate feasible computation over a fairly general notion of data and codata. Specifically, we present a direct Bellantoni-Cook-style normal/safe typed programming formalism…
Two algorithms in search of a type system
Norman Danner, James S. Royer
The authors' ATR programming formalism is a version of call-by-value PCF under a complexity-theoretically motivated type system. ATR programs run in type-2 polynomial-time and all…
Time-complexity semantics for feasible affine recursions (extended abstract)
Norman Danner, James S. Royer
The authors' ATR programming formalism is a version of call-by-value PCF under a complexity-theoretically motivated type system. ATR programs run in type-2 polynomial-time and all…
Adventures in time and space
Norman Danner, James S. Royer
This paper investigates what is essentially a call-by-value version of PCF under a complexity-theoretically motivated type system. The programming formalism, ATR, has its first-ord…
The weak pigeonhole principle for function classes in S^1_2
Norman Danner, Chris Pollett
It is well known that S^1_2 cannot prove the injective weak pigeonhole principle for polynomial time functions unless RSA is insecure. In this note we investigate the provability o…