16 citations · 41 across the 8 of their papers we have counts for
10 papers
Complete and tractable machine-independent characterizations of second-order polytime
Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion +1
The class of Basic Feasible Functionals BFF is the second-order counterpart of the class of first-order functions computable in polynomial time. We present several implicit charact…
Quantum Expectation Transformers for Cost Analysis
Martin Avanzini, Georg Moser, Romain Péchoux +2
We introduce a new kind of expectation transformer for a mixed classical-quantum programming language. Our semantic approach relies on a new notion of a cost structure, which we in…
A tier-based typed programming language characterizing Feasible Functionals
Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion +1
The class of Basic Feasible Functionals BFF is the type-2 counterpart of the class FP of type-1 functions computable in polynomial time. Several characterizations have been sug…
Quantum Programming with Inductive Datatypes: Causality and Affine Type Theory
Romain Péchoux, Simon Perdrix, Mathys Rennela +1
Inductive datatypes in programming languages allow users to define useful data structures such as natural numbers, lists, trees, and others. In this paper we show how inductive dat…
A Type-Based Complexity Analysis of Object Oriented Programs
Emmanuel Hainry, Romain Péchoux
A type system is introduced for a generic Object Oriented programming language in order to infer resource upper bounds. A sound andcomplete characterization of the set of polynomia…
Theory of higher order interpretations and application to Basic Feasible Functions
Emmanuel Hainry, Romain Péchoux
Interpretation methods and their restrictions to polynomials have been deeply used to control the termination and complexity of first-order term rewrite systems. This paper extends…