Programming languages capturing complexity classes

MaRDI QIDQ3370734zbMATH OpenFDO

Authors Lars Kristiansen, Paul J. Voda

Publication date 8 February 2006

zbMATH Keywords

computational complexityhigher typestyped \(\lambda\)-calculi

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• LOGSPACE and PTIME characterized by programming languages
• Some Programming Languages for Logspace and Ptime
• On the computational complexity of imperative programming languages
• Logical Approaches to Computational Barriers
• Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\)

Cited in

(7)

• Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\)
• Computational complexity via programming languages: Constant factors do matter
• The power of non-determinism in higher-order implicit complexity. Characterising complexity classes using non-deterministic cons-free programming
• Recursion in Higher Types and Resource Bounded Turing Machines
• Some Programming Languages for Logspace and Ptime
• Computer Science Logic
• Non-determinism in Gödel's system \(T\)

This page was built for publication: Programming languages capturing complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3370734)