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.

BibTeX

@inproceedings{FNAM-RTA10,
  author      = "Friedrich Neurauter and Aart Middeldorp",
  title       = "Polynomial Interpretations over the Reals do not Subsume
                 Polynomial Interpretations over the Integers",
  booktitle   = "Proceedings of the 21st International Conference on
                 Rewriting Techniques and Applications",
  series      = "Leibniz International Proceedings in Informatics",
  volume      = 6,
  pages       = "243--258",
  year        = 2010
}