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)- Linear pattern matching of compressed terms and polynomial rewriting
- A combination framework for complexity
- (In)efficiency and reasonable cost models
- On the enumeration of closures and environments with an application to random generation
- The exact hardness of deciding derivational and runtime complexity
- Size-based termination of higher-order rewriting
- Complexity analysis by graph rewriting
- A dependency pair framework for innermost complexity analysis of term rewrite systems
- A new order-theoretic characterisation of the polytime computable functions
- Analyzing innermost runtime complexity of term rewriting by dependency pairs
- A characterization of basic feasible functionals through higher-order rewriting and tuple interpretations
- Counting environments and closures
- Gap-languages and log-time complexity classes
- On sharing, memoization, and polynomial time
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)
