Combining linear logic and size types for implicit complexity

DOI10.4230/LIPICS.CSL.2018.9MaRDI QIDQ5079730FDOQ5079730

Authors: Patrick Baillot, Alexis Ghyselen 

Publication date: 28 May 2022

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

zbMATH Keywords

implicit computational complexitylinear logic\(\lambda\)-calculustype systemspolynomial time complexitysize types

Mathematics Subject Classification ID

Logic in computer science (03B70)

Cites Work

• A new recursion-theoretic characterization of the polytime functions
• Light linear logic
• Linear types and non-size-increasing polynomial time computation.
• Linear logic and elementary time
• Higher-order interpretations and program complexity
• A polytime functional language from light linear logic
• Title not available (Why is that?)
• Linear dependent types and relative completeness
• Multivariate amortized resource analysis
• Quasi-interpretations. A way to control resources
• Typed Lambda Calculi and Applications
• Static prediction of heap space usage for first-order functional programs
• Amortized resource analysis with polynomial potential. A static inference of polynomial bounds for functional programs
• An elementary affine \(\lambda \)-calculus with multithreading and side effects
• Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus
• Static determination of quantitative resource usage for higher-order programs
• 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
• A higher-order characterization of probabilistic polynomial time
• Implicit Computational Complexity of Subrecursive Definitions and Applications to Cryptographic Proofs

Cited In (3)

• Combining linear logic and size types for implicit complexity
• Title not available (Why is that?)
• Causal computational complexity of distributed processes

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)