A Short Introduction to Implicit Computational Complexity

DOI10.1007/978-3-642-31485-8_3MaRDI QIDQ3166988zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Developments in implicit computational complexity
• SOFSEM 2006: Theory and Practice of Computer Science
• scientific article; zbMATH DE number 1980917
• Guest editorial: Special issue on implicit computational complexity
• scientific article; zbMATH DE number 4009816
• An overview of computational complexity
• scientific article; zbMATH DE number 1948174
• Developments in implicit complexity (DICE 2012)
• A short note on integer complexity

Cites work

• A new recursion-theoretic characterization of the polytime functions
• Algorithms with polynomial interpretation termination proof
• Analysing the implicit complexity of programs.
• Computational Complexity
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 5318491 (Why is no real title available?)
• scientific article; zbMATH DE number 3700811 (Why is no real title available?)
• scientific article; zbMATH DE number 512786 (Why is no real title available?)
• scientific article; zbMATH DE number 2079048 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• Light affine lambda calculus and polynomial time strong normalization
• Light linear logic
• Linear types and non-size-increasing polynomial time computation.
• On Computable Numbers, with an Application to the Entscheidungsproblem
• On the Computational Complexity of Algorithms
• On the computational complexity of imperative programming languages
• Programming Languages and Systems
• Quasi-interpretations. A way to control resources
• Soft linear logic and polynomial time
• Term Rewriting and All That
• The lambda calculus. Its syntax and semantics. Rev. ed.

Cited in

(10)

• Developments in implicit computational complexity
• Mitigating multi-target attacks in hash-based signatures
• Unary resolution: characterizing \textsc{Ptime}
• Towards a formal theory of graded monads
• Probabilistic termination by monadic affine sized typing
• The power of non-determinism in higher-order implicit complexity. Characterising complexity classes using non-deterministic cons-free programming
• Implicit Computational Complexity of Subrecursive Definitions and Applications to Cryptographic Proofs
• scientific article; zbMATH DE number 1980917 (Why is no real title available?)
• Implicit computation complexity in higher-order programming languages
• A programming language characterizing quantum polynomial time

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

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