Zobrazeno 1 - 10
of 49
pro vyhledávání: '"Royer, James S."'
Autor:
Danner, Norman, Royer, James S.
We exhibit a sound and complete implicit-complexity formalism for functions feasibly computable by structural recursions over inductively defined data structures. Feasibly computable here means that the structural-recursive definition runs in time po
Externí odkaz:
http://arxiv.org/abs/2205.10348
Autor:
Danner, Norman, Royer, James S.
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, RS1, that expresses feasible structural recursions and corecursions
Externí odkaz:
http://arxiv.org/abs/1201.4567
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 resource bound} $\Delta$, which is a class of functions. When $\Delta
Externí odkaz:
http://arxiv.org/abs/1102.2095
Autor:
Danner, Norman, Royer, James S.
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 standard type-2 basic feasible functionals are ATR-definable (ATR type
Externí odkaz:
http://arxiv.org/abs/0710.0824
Autor:
Danner, Norman, Royer, James S.
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 standard type-2 basic feasible functionals are ATR-definable (ATR type
Externí odkaz:
http://arxiv.org/abs/cs/0701076
Autor:
Danner, Norman, Royer, James S.
Publikováno v:
Logical Methods in Computer Science, Volume 3, Issue 1 (March 12, 2007) lmcs:2231
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-order programs characterize the polynomial-time computable functions, and
Externí odkaz:
http://arxiv.org/abs/cs/0612116
Publikováno v:
The Journal of Symbolic Logic, 2004 Sep 01. 69(3), 713-741.
Externí odkaz:
https://www.jstor.org/stable/30041754
Autor:
Royer, James S.
Publikováno v:
The Journal of Symbolic Logic, 1989 Jun 01. 54(2), 522-526.
Externí odkaz:
https://www.jstor.org/stable/2274866
Publikováno v:
In Annals of Pure and Applied Logic 2006 139(1):303-326