A Short Introduction to Implicit Computational Complexity

DOI10.1007/978-3-642-31485-8_3zbMath1250.03066OpenAlexW69987426MaRDI QIDQ3166988

Ugo Dal Lago

Publication date: 1 November 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-31485-8_3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

A programming language characterizing quantum polynomial time ⋮ Probabilistic Termination by Monadic Affine Sized Typing ⋮ The Power of Non-determinism in Higher-Order Implicit Complexity ⋮ Mitigating Multi-target Attacks in Hash-Based Signatures ⋮ Unary Resolution: Characterizing Ptime ⋮ Towards a Formal Theory of Graded Monads

Cites Work

• Quasi-interpretations. A way to control resources
• The lambda calculus. Its syntax and semantics. Rev. ed.
• Light affine lambda calculus and polynomial time strong normalization
• A new recursion-theoretic characterization of the polytime functions
• Light linear logic
• Analysing the implicit complexity of programs.
• Linear types and non-size-increasing polynomial time computation.
• On the computational complexity of imperative programming languages
• Soft linear logic and polynomial time
• Algorithms with polynomial interpretation termination proof
• Term Rewriting and All That
• Computational Complexity
• On the Computational Complexity of Algorithms
• Programming Languages and Systems
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A Short Introduction to Implicit Computational Complexity