Bounded combinatory logic and lower complexity

DOI10.1016/j.ic.2015.12.013zbMath1339.68140OpenAlexW2229623334MaRDI QIDQ276270

Brian F. Redmond

Publication date: 3 May 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2015.12.013

zbMATH Keywords

stratificationpolynomial timeimplicit computational complexitycombinatory logicpolynomial spacesoft linear logic

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47) Combinatory logic and lambda calculus (03B40)

Related Items (1)

Implicit computation complexity in higher-order programming languages

Cites Work

• Unnamed Item
• Unnamed Item
• Safe recursion revisited. I: Categorical semantics for lower complexity
• The parametric lambda calculus. A metamodel for computation.
• Characterizing complexity classes by higher type primitive recursive definitions
• A new recursion-theoretic characterization of the polytime functions
• Light linear logic
• Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
• Interaction combinators
• Linear types and non-size-increasing polynomial time computation.
• Linear logic and elementary time
• Soft linear logic and polynomial time
• The expressive power of higher-order types or, life without CONS
• Soft Linear Logic and Polynomial Complexity Classes
• A Categorical Setting for Lower Complexity
• A logical account of pspace
• Semantic Evaluation, Intersection Types and Complexity of Simply Typed Lambda Calculus

This page was built for publication: Bounded combinatory logic and lower complexity