Analysing the implicit complexity of programs.
From MaRDI portal
Publication:1401939
DOI10.1016/S0890-5401(03)00011-7zbMath1054.68073MaRDI QIDQ1401939
Publication date: 19 August 2003
Published in: Information and Computation (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) General topics in the theory of software (68N01)
Related Items (13)
A Short Introduction to Implicit Computational Complexity ⋮ On sharing, memoization, and polynomial time ⋮ On quasi-interpretations, blind abstractions and implicit complexity ⋮ Proving Quadratic Derivational Complexities Using Context Dependent Interpretations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Automated Implicit Computational Complexity Analysis (System Description) ⋮ Quasi-interpretations. A way to control resources ⋮ On the relative power of polynomials with real, rational, and integer coefficients in proofs of termination of rewriting ⋮ Complexity Analysis by Rewriting ⋮ Dependency Pairs and Polynomial Path Orders ⋮ CoLoR: a Coq library on well-founded rewrite relations and its application to the automated verification of termination certificates ⋮ A new order-theoretic characterisation of the polytime computable functions
Cites Work
- Orderings for term-rewriting systems
- Termination of rewriting
- The realm of primitive recursion
- Termination proofs by multiset path orderings imply primitive recursive derivation lengths
- A new recursion-theoretic characterization of the polytime functions
- Results and trends in theoretical computer science, Colloquium in honor of Arto Salomaa, Graz, Austria, June 10-11, 1994. Proceedings
- Automated complexity analysis of Nuprl extracted programs
- Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Analysing the implicit complexity of programs.
