Friedrich Neurauter ; Aart Middeldorp - Polynomial Interpretations over the Natural, Rational and Real Numbers Revisited

lmcs:853 - Logical Methods in Computer Science, September 18, 2014, Volume 10, Issue 3 - https://doi.org/10.2168/LMCS-10(3:22)2014
Polynomial Interpretations over the Natural, Rational and Real Numbers Revisited

Authors: Friedrich Neurauter ; Aart Middeldorp

Polynomial interpretations are a useful technique for proving termination of term rewrite systems. They come in various flavors: polynomial interpretations with real, rational and integer coefficients. As to their relationship with respect to termination proving power, Lucas managed to prove in 2006 that there are rewrite systems that can be shown polynomially terminating by polynomial interpretations with real (algebraic) coefficients, but cannot be shown polynomially terminating using polynomials with rational coefficients only. He also proved the corresponding statement regarding the use of rational coefficients versus integer coefficients. In this article we extend these results, thereby giving the full picture of the relationship between the aforementioned variants of polynomial interpretations. In particular, we show that polynomial interpretations with real or rational coefficients do not subsume polynomial interpretations with integer coefficients. Our results hold also for incremental termination proofs with polynomial interpretations.


Volume: Volume 10, Issue 3
Published on: September 18, 2014
Accepted on: June 25, 2015
Submitted on: October 27, 2010
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 351 times.
This article's PDF has been downloaded 763 times.