31 citations · 38 across the 7 of their papers we have counts for
7 papers
General Ramified Recurrence and Polynomial-time Completeness
Norman Danner, James S. Royer
We exhibit a sound and complete implicit-complexity formalism for functions feasibly computable by structural recursions over inductively defined data structures. Feasibly computab…
A static cost analysis for a higher-order language
N. Danner, J. Paykin, J. S. Royer
We develop a static complexity analysis for a higher-order functional language with structural list recursion. The complexity of an expression is a pair consisting of a cost and a…
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…
Axiomatizing Resource Bounds for Measure
Xiaoyang Gu, Jack H. Lutz, Satyadev Nandakumar +1
Resource-bounded measure is a generalization of classical Lebesgue measure that is useful in computational complexity. The central parameter of resource-bounded measure is the {\it…
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…