Polynomial time over the reals with parsimony

DOI10.1007/978-3-030-59025-3_4OpenAlexW3009846165MaRDI QIDQ2039933

Emmanuel Hainry, Damiano Mazza, Romain Péchoux

Publication date: 6 July 2021

Full work available at URL: https://hal.inria.fr/hal-02499149/file/main.pdf

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18) Logic programming (68N17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Proofs, programs, processes
• Type inference for light affine logic via constraints on words
• A certified, corecursive implementation of exact real numbers
• Light types for polynomial time computation in lambda calculus
• Light linear logic
• Feasible real random access machines
• Infinitary lambda calculus
• Linear types and non-size-increasing polynomial time computation.
• The differential lambda-calculus
• Characterizing polynomial time complexity of stream programs using interpretations
• Complexity Theory for Operators in Analysis
• The Computational Contents of Ramified Corecurrence
• Algebras and coalgebras in the light affine Lambda calculus
• From coinductive proofs to exact real arithmetic: theory and applications
• Parsimonious Types and Non-uniform Computation
• A Soft Type Assignment System for λ-Calculus
• A Theory of Program Size Formally Identical to Information Theory
• Beta reduction is invariant, indeed
• Infinitary Lambda Calculi from a Linear Perspective
• A Language for Differentiable Functions
• Simple Parsimonious Types and Logarithmic Space
• Verification of Ptime Reducibility for system F Terms: Type Inference in Dual Light Affine Logic