Tiered complexity at higher order

Emmanuel Hainry (1) , Bruce Kapron (2) , Jean-Yves Marion (3) , Romain Péchoux (1)

1 MOCQUA - Designing the Future of Computational Models
2 UVIC - University of Victoria [Canada]
3 CARBONE - Carbone

A characterization of the class of Basic Feasible Functionals (BFF) is provided in terms of typable and terminating imperative programs with oracles. The type system is a tier-based type system and type inference can be done in polynomial time.

Domaines: Complexité [cs.CC]; Logique en informatique [cs.LO]

Emmanuel Hainry, Bruce Kapron, Jean-Yves Marion, Romain Péchoux. Tiered complexity at higher order. DICE-FOPARA 2019 - Joint international workshop on Developments in Implicit Computational complExity and Foundational and Practical Aspects of Resource Analysis, Apr 2019, Praha, Czech Republic. ⟨hal-02499318⟩