Real or natural number interpretation and their effect on complexity

DOI10.1016/j.tcs.2015.03.004zbMath1345.68188OpenAlexW2073388164MaRDI QIDQ2346989

Guillaume Bonfante, Florian Deloup, Antoine Henrot

Publication date: 26 May 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.03.004

zbMATH Keywords

term rewritingalgebraic geometryimplicit computational complexitypolynomial interpretation

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Real algebraic and real-analytic geometry (14P99)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on simplification orderings
• Testing positiveness of polynomials
• Termination of term rewriting using dependency pairs
• On the relative power of polynomials with real, rational, and integer coefficients in proofs of termination of rewriting
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Algorithms with polynomial interpretation termination proof
• Sup-interpretations, a semantic method for static analysis of program resources
• Resource Analysis by Sup-interpretation
• Proving Quadratic Derivational Complexities Using Context Dependent Interpretations
• Termination of String Rewriting with Matrix Interpretations
• Automated Complexity Analysis Based on the Dependency Pair Method
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Termination proofs and the length of derivations
• Complexity Analysis by Rewriting
• Tree-Manipulating Systems and Church-Rosser Theorems
• Derivational Complexity Is an Invariant Cost Model
• Algorithms in real algebraic geometry
• Dynamical method in algebra: Effective Nullstellensätze