首页    期刊浏览 2024年11月13日 星期三
登录注册

文章基本信息

  • 标题:Polynomial Interpretations over the Reals do not Subsume Polynomial Interpretations over the Integers
  • 本地全文:下载
  • 作者:Friedrich Neurauter ; Aart Middeldorp
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2010
  • 卷号:6
  • 页码:243-258
  • DOI:10.4230/LIPIcs.RTA.2010.243
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:Term rewriting; termination; polynomial interpretations
国家哲学社会科学文献中心版权所有