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

lmcs:853 - Logical Methods in Computer Science, September 18, 2014, Volume 10, Issue 3
Polynomial Interpretations over the Natural, Rational and Real Numbers Revisited

Authors: Neurauter, Friedrich and Middeldorp, Aart

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.


Source : oai:arXiv.org:1407.0406
DOI : 10.2168/LMCS-10(3:22)2014
Volume: Volume 10, Issue 3
Published on: September 18, 2014
Submitted on: October 27, 2010
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 91 times.
This article's PDF has been downloaded 146 times.