The expressive power of higher-order types or, life without CONS
From MaRDI portal
Publication:2740986
DOI10.1017/S0956796800003889zbMath0988.68046OpenAlexW2105438076WikidataQ128378970 ScholiaQ128378970MaRDI QIDQ2740986
Publication date: 9 April 2002
Published in: Journal of Functional Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0956796800003889
Functional programming and lambda calculus (68N18) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Computation by interaction for space-bounded functional programming, Bounded combinatory logic and lower complexity, Characterizing polynomial and exponential complexity classes in elementary lambda-calculus, Computational Complexity Via Finite Types, Unnamed Item, A Characterisation of the Relations Definable in Presburger Arithmetic, Subclasses of \textsc{Ptime} interpreted by programming languages, Read/write factorizable programs, The Expressive Power of Higher-Order Datalog, Pure Iteration and Periodicity, Recursion in Higher Types and Resource Bounded Turing Machines, Unnamed Item, The Power of Non-determinism in Higher-Order Implicit Complexity, Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH, Implicit complexity over an arbitrary structure: Quantifier alternations, Bounded minimalisation and bounded counting in argument-bounded idc's, Two algorithms in search of a type-system, Unnamed Item, Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\), Complexity classes and fragments of C, The Complexity of Model-Checking Tail-Recursive Higher-Order Fixpoint Logic, On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
Uses Software
