Abstract

In this paper we prove that the problem whether the termination of a given rewrite system can be shown by a polynomial interpretation in the natural numbers is undecidable.

BibTeX Entry

@inproceedings{MM-WST21,
 author    = "Fabian Mitterwallner and Aart Middeldorp",
 title     = "Polynomial Termination over {N} is Undecidable",
 booktitle = "Proceedings of the 17th International Workshop on
              Termination",
 editor    = "Samir Genaim",
 pages     = "21--26",
 year      = 2021
}