Real or natural number interpretation and their effect on complexity
From MaRDI portal
Publication:2346989
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
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