Implicit computation complexity in higher-order programming languages
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 1948174
- On the computational complexity of imperative programming languages
- Analysing the implicit complexity of programs.
- The power of non-determinism in higher-order implicit complexity. Characterising complexity classes using non-deterministic cons-free programming
- Higher-order interpretations and program complexity
- Higher-order interpretations and program complexity
- Developments in implicit computational complexity
- scientific article; zbMATH DE number 177794
- A Short Introduction to Implicit Computational Complexity
Cites work
- (Optimal) duplication is not elementary recursive
- \(\lambda\)-definability of free algebras
- A By-Level Analysis of Multiplicative Exponential Linear Logic
- A characterization of lambda definable tree operations
- A new recursion-theoretic characterization of the polytime functions
- A new “feasible” arithmetic
- A recursion-theoretic approach to NP
- A semantic proof of polytime soundness of light affine logic
- A Soft Type Assignment System for λ-Calculus
- A type system for bounded space and functional in-place update
- Algebras and coalgebras in the light affine lambda calculus
- An abstract approach to stratification in linear logic
- An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras
- An arithmetic for non-size-increasing polynomial-time computation
- An extension of basic functionality theory for -calculus
- An implicit characterization of PSPACE
- Bounded combinatory logic and lower complexity
- Bounded linear logic, revisited
- Bounded linear logic: A modular approach to polynomial-time computability
- Characterizing complexity classes by general recursive definitions in higher types
- Characterizing complexity classes by higher type primitive recursive definitions
- Characterizing PSPACE with pointers
- Computation by interaction for space-bounded functional programming
- Computational Complexity
- Computational Complexity
- Context semantics, linear logic, and computational complexity
- Elementary complexity and geometry of interaction
- Existence and feasibility in arithmetic
- Foundations of Software Science and Computation Structures
- Functional interpretations of feasibly constructive arithmetic
- FUNCTIONAL PEARL Linear lambda calculus and PTIME-completeness
- Functional programming in sublinear space
- Higher type recursion, ramification and polynomial time
- scientific article; zbMATH DE number 4059391 (Why is no real title available?)
- scientific article; zbMATH DE number 42059 (Why is no real title available?)
- scientific article; zbMATH DE number 1223626 (Why is no real title available?)
- scientific article; zbMATH DE number 1229489 (Why is no real title available?)
- scientific article; zbMATH DE number 2079048 (Why is no real title available?)
- scientific article; zbMATH DE number 1392281 (Why is no real title available?)
- scientific article; zbMATH DE number 1424029 (Why is no real title available?)
- scientific article; zbMATH DE number 1424054 (Why is no real title available?)
- scientific article; zbMATH DE number 3305097 (Why is no real title available?)
- Infinitary lambda calculi from a linear perspective
- Intuitionistic light affine logic
- Lectures on the Curry-Howard isomorphism
- Light affine lambda calculus and polynomial time strong normalization
- Light affine set theory: A naive set theory of polynomial time
- Light linear logic
- Light logics and higher-order processes
- Light logics and optimal reduction: completeness and complexity
- Light Logics and the Call-by-Value Lambda Calculus
- Light types for polynomial time computation in lambda calculus
- Linear dependent types and relative completeness
- Linear dependent types in a call-by-value scenario
- Linear logic and elementary time
- Linear logic and polynomial time
- Linear logic by levels and bounded time complexity
- Linear types and non-size-increasing polynomial time computation.
- Multiplexor Categories and Models of Soft Linear Logic
- Non-uniform polytime computation in the infinitary affine lambda-calculus
- On an interpretation of safe recursion in light affine logic
- On equivalences, metrics, and polynomial time
- On light logics, uniform encodings and polynomial time
- On session types and polynomial time
- On sharing, memoization, and polynomial time
- On the Computational Complexity of Algorithms
- On the computational complexity of cut-elimination in linear logic.
- On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
- Optimizing optimal reduction
- Parsimonious types and non-uniform computation
- Polynomial Time in the Parametric Lambda Calculus.
- Programming Languages and Systems
- Quantum implicit computational complexity
- Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
- Realizability models and implicit complexity
- Realizability models for BLL-like languages
- Safe recursion with higher types and BCK-algebra
- Semantic evaluation; intersection types and complexity of simply typed lambda calculus
- Simple parsimonious types and logarithmic space
- Soft linear logic and polynomial time
- Soft linear set theory
- Static determination of quantitative resource usage for higher-order programs
- Stratified coherence spaces: A denotational semantics for light linear logic
- The Computational SLR: A Logic for Reasoning about Computational Indistinguishability
- The Expressiveness of Simple and Second-Order Type Structures
- The geometry of linear higher-order recursion
- The geometry of types
- The strength of non-size increasing computation
- Verification of Ptime Reducibility for system F Terms: Type Inference in Dual Light Affine Logic
Cited in
(5)- The power of non-determinism in higher-order implicit complexity. Characterising complexity classes using non-deterministic cons-free programming
- Proofs as efficient programs
- Read/write factorizable programs
- Consistent ultrafinitist logic
- Towards a characterization of two-way bijections in a reversible computational model
This page was built for publication: Implicit computation complexity in higher-order programming languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875893)
