Bounded combinatory logic and lower complexity

DOI10.1016/J.IC.2015.12.013MaRDI QIDQ276270zbMATH OpenOpenAlexFDO

Authors Brian 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

stratificationcombinatory logicimplicit computational complexitypolynomial spacepolynomial timesoft linear logic

Mathematics Subject Classification ID

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

Recommendations

• Soft linear logic and polynomial complexity classes
• Linear logic by levels and bounded time complexity
• Bounded linear logic: A modular approach to polynomial-time computability
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• Bounded combinatory logic

Cites work

• scientific article; zbMATH DE number 5318491 (Why is no real title available?)
• scientific article; zbMATH DE number 2079048 (Why is no real title available?)
• A categorical setting for lower complexity
• A logical account of pspace
• A new recursion-theoretic characterization of the polytime functions
• Characterizing complexity classes by higher type primitive recursive definitions
• Interaction combinators
• Light linear logic
• Linear logic and elementary time
• Linear types and non-size-increasing polynomial time computation.
• Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
• Safe recursion revisited. I: Categorical semantics for lower complexity
• Semantic evaluation; intersection types and complexity of simply typed lambda calculus
• Soft linear logic and polynomial complexity classes
• Soft linear logic and polynomial time
• The expressive power of higher-order types or, life without CONS
• The parametric lambda calculus. A metamodel for computation.

Cited in

(6)

• Restricted combinatory unification
• scientific article; zbMATH DE number 2044514 (Why is no real title available?)
• Compact bracket abstraction in combinatory logic
• Implicit computation complexity in higher-order programming languages
• Bounded combinatory logic
• Polytime, combinatory logic and positive safe induction

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q276270)