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 RevisitedArticle

Authors: Friedrich Neurauter ; Aart Middeldorp ORCID

    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
    Imported on: October 27, 2010
    Keywords: Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 1067 times.
    This article's PDF has been downloaded 891 times.