2026-07-23T04:16:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2656 2024-03-06T10:33:29Z ddc:004 open_access

Polynomial Interpretations over the Reals do not Subsume Polynomial Interpretations over the Integers Neurauter, Friedrich Middeldorp, Aart Term rewriting termination polynomial interpretations 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Friedrich Neurauter and Aart Middeldorp 2010 Is Part Of LIPIcs, Volume 6, Proceedings of the 21st International Conference on Rewriting Techniques and Applications (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.RTA.2010.243 urn:nbn:de:0030-drops-26565 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2010.243 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode