License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2010.243
URN: urn:nbn:de:0030-drops-26565
URL: https://drops.dagstuhl.de/opus/volltexte/2010/2656/
Go to the corresponding LIPIcs Volume Portal

Neurauter, Friedrich ; Middeldorp, Aart

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

pdf-format:
10002.NaurauterFriedrich.2656.pdf (0.2 MB)

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 - Entry

@InProceedings{neurauter_et_al:LIPIcs:2010:2656,
  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},
  pages =	{243--258},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{6},
  editor =	{Christopher Lynch},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2656},
  URN =		{urn:nbn:de:0030-drops-26565},
  doi =		{10.4230/LIPIcs.RTA.2010.243},
  annote =	{Keywords: Term rewriting, termination, polynomial interpretations}
}

Keywords: Term rewriting, termination, polynomial interpretations
Collection: Proceedings of the 21st International Conference on Rewriting Techniques and Applications
Issue Date: 2010
Date of publication: 06.07.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI