Combining linear logic and size types for implicit complexity

DOI10.4230/LIPICS.CSL.2018.9MaRDI QIDQ5079730zbMATH OpenFDO

Authors Patrick Baillot, Alexis Ghyselen

Publication date 28 May 2022

Full work available at URL https://doi.org/10.4230/LIPICS.CSL.2018.9

zbMATH Keywords

\(\lambda\)-calculusimplicit computational complexitylinear logicpolynomial time complexitysize typestype systems

Mathematics Subject Classification ID

Logic in computer science (03B70)

Recommendations

• Combining linear logic and size types for implicit complexity
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• Complexity analysis in presence of control operators and higher-order functions
• Linear logic by levels and bounded time complexity
• Soft linear logic and polynomial complexity classes

Cites work

• A higher-order characterization of probabilistic polynomial time
• A new recursion-theoretic characterization of the polytime functions
• A polytime functional language from light linear logic
• Amortized resource analysis with polynomial potential. A static inference of polynomial bounds for functional programs
• An elementary affine -calculus with multithreading and side effects
• Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus
• Higher-order interpretations and program complexity
• scientific article; zbMATH DE number 1223626 (Why is no real title available?)
• Implicit Computational Complexity of Subrecursive Definitions and Applications to Cryptographic Proofs
• Light linear logic
• Linear dependent types and relative completeness
• Linear dependent types in a call-by-value scenario
• Linear logic and elementary time
• Linear types and non-size-increasing polynomial time computation.
• Multivariate amortized resource analysis
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• Quasi-interpretations. A way to control resources
• Static determination of quantitative resource usage for higher-order programs
• Static prediction of heap space usage for first-order functional programs
• The geometry of types
• Typed Lambda Calculi and Applications

Cited in

(3)

• Combining linear logic and size types for implicit complexity
• Causal computational complexity of distributed processes
• scientific article; zbMATH DE number 7561616 (Why is no real title available?)

This page was built for publication: Combining linear logic and size types for implicit complexity

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