Closing the gap between runtime complexity and polytime computability
From MaRDI portal
Recommendations
- Complexity analysis by graph rewriting
- A term rewriting characterization of the polytime functions and related complexity classes
- A new order-theoretic characterisation of the polytime computable functions
- scientific article; zbMATH DE number 1342224
- The exact hardness of deciding derivational and runtime complexity
Cited in
(14)- Gap-languages and log-time complexity classes
- On sharing, memoization, and polynomial time
- (In)efficiency and reasonable cost models
- A new order-theoretic characterisation of the polytime computable functions
- Analyzing innermost runtime complexity of term rewriting by dependency pairs
- A combination framework for complexity
- The exact hardness of deciding derivational and runtime complexity
- Complexity analysis by graph rewriting
- Size-based termination of higher-order rewriting
- Linear pattern matching of compressed terms and polynomial rewriting
- On the enumeration of closures and environments with an application to random generation
- Counting environments and closures
- A dependency pair framework for innermost complexity analysis of term rewrite systems
- A characterization of basic feasible functionals through higher-order rewriting and tuple interpretations
This page was built for publication: Closing the gap between runtime complexity and polytime computability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5389134)
