Implicit computation complexity in higher-order programming languages
From MaRDI portal
Publication:5875893
DOI10.1017/S0960129521000505OpenAlexW4220779078MaRDI QIDQ5875893FDOQ5875893
Authors: Ugo Dal Lago 
Publication date: 6 February 2023
Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0960129521000505
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
- Computational Complexity
- On the Computational Complexity of Algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lectures on the Curry-Howard isomorphism
- Light types for polynomial time computation in lambda calculus
- An extension of basic functionality theory for \(\lambda\)-calculus
- Characterizing complexity classes by higher type primitive recursive definitions
- Bounded linear logic: A modular approach to polynomial-time computability
- A new recursion-theoretic characterization of the polytime functions
- Light linear logic
- Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
- Linear types and non-size-increasing polynomial time computation.
- Linear logic and elementary time
- Higher type recursion, ramification and polynomial time
- Safe recursion with higher types and BCK-algebra
- Soft linear logic and polynomial time
- Elementary complexity and geometry of interaction
- Computation by interaction for space-bounded functional programming
- Bounded combinatory logic and lower complexity
- Functional programming in sublinear space
- A Soft Type Assignment System for λ-Calculus
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Linear dependent types and relative completeness
- Semantic evaluation; intersection types and complexity of simply typed lambda calculus
- Realizability models and implicit complexity
- Verification of Ptime Reducibility for system F Terms: Type Inference in Dual Light Affine Logic
- Programming Languages and Systems
- On light logics, uniform encodings and polynomial time
- Existence and feasibility in arithmetic
- Intuitionistic light affine logic
- On the computational complexity of cut-elimination in linear logic.
- Computational Complexity
- Light affine lambda calculus and polynomial time strong normalization
- Title not available (Why is that?)
- The geometry of linear higher-order recursion
- On an interpretation of safe recursion in light affine logic
- Light affine set theory: A naive set theory of polynomial time
- Linear logic and polynomial time
- Title not available (Why is that?)
- Title not available (Why is that?)
- \(\lambda\)-definability of free algebras
- Stratified coherence spaces: A denotational semantics for light linear logic
- Realizability models for BLL-like languages
- Context semantics, linear logic, and computational complexity
- The Expressiveness of Simple and Second-Order Type Structures
- Foundations of Software Science and Computation Structures
- Functional interpretations of feasibly constructive arithmetic
- A semantic proof of polytime soundness of light affine logic
- (Optimal) duplication is not elementary recursive
- Optimizing optimal reduction
- Light logics and optimal reduction: completeness and complexity
- Characterizing PSPACE with pointers
- A recursion-theoretic approach to NP
- An arithmetic for non-size-increasing polynomial-time computation
- A new “feasible” arithmetic
- A type system for bounded space and functional in-place update
- The strength of non-size increasing computation
- A characterization of lambda definable tree operations
- Soft linear set theory
- Infinitary lambda calculi from a linear perspective
- Quantum implicit computational complexity
- Linear logic by levels and bounded time complexity
- Title not available (Why is that?)
- An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras
- On sharing, memoization, and polynomial time
- Characterizing complexity classes by general recursive definitions in higher types
- Bounded linear logic, revisited
- Light Logics and the Call-by-Value Lambda Calculus
- The Computational SLR: A Logic for Reasoning about Computational Indistinguishability
- Static determination of quantitative resource usage for higher-order programs
- An abstract approach to stratification in linear logic
- Polynomial Time in the Parametric Lambda Calculus.
- On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
- Linear dependent types in a call-by-value scenario
- The geometry of types
- An implicit characterization of PSPACE
- Algebras and coalgebras in the light affine lambda calculus
- Parsimonious types and non-uniform computation
- Simple parsimonious types and logarithmic space
- Light logics and higher-order processes
- On session types and polynomial time
- FUNCTIONAL PEARL Linear lambda calculus and PTIME-completeness
- A By-Level Analysis of Multiplicative Exponential Linear Logic
- Multiplexor Categories and Models of Soft Linear Logic
- On equivalences, metrics, and polynomial time
- Non-uniform polytime computation in the infinitary affine lambda-calculus
Cited In (3)
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)
