Bounded Combinatory Logic and lower complexity

We introduce a stratified version of Combinatory Logic 1 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.

Authors

• Brian F. Redmond

Keywords

• Combinatory Logic
• Stratification
• Implicit computational complexity
• Polynomial time and space
• Soft linear logic