Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426385 | Information and Computation | 2016 | 12 Pages |
Abstract
We introduce a stratified version of Combinatory Logic1 in which there are two classes of terms called player and opponent such that the class of player terms is strictly contained in the class of opponent terms. We show that the system characterizes Polynomial Time in a similar way to Soft Linear Logic. With the addition of explicit “lazy” products to the player terms and various notions of distributivity, we obtain a characterization of Polynomial Space. This paper is an expanded version of the abstract presented at DICE 2013.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Brian F. Redmond,