Polynomial interpretations and the complexity of algorithms

DOI10.1007/3-540-55602-8_161MaRDI QIDQ4264735zbMATH OpenFDO

Authors A. Cichon, Pierre Lescanne

Publication date 10 October 1999

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

Full work available at URL https://doi.org/10.1007/3-540-55602-8_161

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Recommendations

• scientific article; zbMATH DE number 4110084
• Algorithms with polynomial interpretation termination proof
• Complexity classes and rewrite systems with polynomial interpretation
• scientific article; zbMATH DE number 1722702
• Polynomial interpretations over the natural, rational and real numbers revisited

Cited in

(23)

• Algebraic complexity of computing polynomial zeros
• Applications and extensions of context-sensitive rewriting
• Derivational complexity and context-sensitive Rewriting
• Real or natural number interpretation and their effect on complexity
• On the relative power of polynomials with real, rational, and integer coefficients in proofs of termination of rewriting
• Algorithms with polynomial interpretation termination proof
• Intensional properties of polygraphs
• Proving Quadratic Derivational Complexities Using Context Dependent Interpretations
• Complexity invariance of real interpretations
• scientific article; zbMATH DE number 4051037 (Why is no real title available?)
• scientific article; zbMATH DE number 4110084 (Why is no real title available?)
• Complexity classes and rewrite systems with polynomial interpretation
• Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
• Theorem proving with group presentations: examples and questions
• A poly-algorithmic approach to simplifying elementary functions
• On the Complexity of the Interlace Polynomial
• Formalizing termination proofs under polynomial quasi-interpretations
• Towards the average-case analysis of substitution resolution in \(\lambda\)-calculus
• Theory of higher order interpretations and application to basic feasible functions
• Polynomials over the reals in proofs of termination : from theory to practice
• Analyzing Innermost Runtime Complexity Through Tuple Interpretations
• Polynomial termination over \(\mathbb{N}\) is undecidable
• Small term reachability and related problems for terminating term rewriting systems

This page was built for publication: Polynomial interpretations and the complexity of algorithms

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