Skip to Main content Skip to Navigation
Conference papers

Polynomial time over the reals with parsimony

Abstract : We provide a characterization of Ko's class of polynomial time computable functions over real numbers. This characterization holds for a stream based language using a parsimonious type discipline, a variant of propositional linear logic. We obtain a first characterization of polynomial time computations over the reals on a higher-order functional language using a linear/affine type system.
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Romain Péchoux Connect in order to contact the contributor
Submitted on : Friday, March 6, 2020 - 9:56:08 AM
Last modification on : Thursday, January 20, 2022 - 5:29:00 PM
Long-term archiving on: : Sunday, June 7, 2020 - 1:05:33 PM


Files produced by the author(s)


  • HAL Id : hal-02499149, version 1


Emmanuel Hainry, Damiano Mazza, Romain Péchoux. Polynomial time over the reals with parsimony. FLOPS 2020 - International Symposium on Functional and Logic Programming, Apr 2020, Akita, Japan. ⟨hal-02499149⟩



Les métriques sont temporairement indisponibles