Polynomial Interpretations over the Reals do not Subsume Polynomial Interpretations over the Integers

Authors Friedrich Neurauter, Aart Middeldorp



PDF
Thumbnail PDF

File

LIPIcs.RTA.2010.243.pdf
  • Filesize: 160 kB
  • 16 pages

Document Identifiers

Author Details

Friedrich Neurauter
Aart Middeldorp

Cite AsGet BibTex

Friedrich Neurauter and Aart Middeldorp. Polynomial Interpretations over the Reals do not Subsume Polynomial Interpretations over the Integers. In Proceedings of the 21st International Conference on Rewriting Techniques and Applications. Leibniz International Proceedings in Informatics (LIPIcs), Volume 6, pp. 243-258, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/LIPIcs.RTA.2010.243

Abstract

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. In 2006, Lucas proved 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 a similar theorem with respect to the use of rational coefficients versus integer coefficients. In this paper we show that polynomial interpretations with real or rational coefficients do not subsume polynomial interpretations with integer coefficients, contrary to what is commonly believed. We further show that polynomial interpretations with real coefficients subsume polynomial interpretations with rational coefficients.
Keywords
  • Term rewriting
  • termination
  • polynomial interpretations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail