Search Results

Documents authored by Mitterwallner, Fabian


Document
Polynomial Termination Over ℕ Is Undecidable

Authors: Fabian Mitterwallner and Aart Middeldorp

Published in: LIPIcs, Volume 228, 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)


Abstract
In this paper we prove via a reduction from Hilbert’s 10th problem that the problem whether the termination of a given rewrite system can be shown by a polynomial interpretation in the natural numbers is undecidable, even for rewrite systems that are incrementally polynomially terminating. We also prove that incremental polynomial termination is an undecidable property of terminating rewrite systems.

Cite as

Fabian Mitterwallner and Aart Middeldorp. Polynomial Termination Over ℕ Is Undecidable. In 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 228, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{mitterwallner_et_al:LIPIcs.FSCD.2022.27,
  author =	{Mitterwallner, Fabian and Middeldorp, Aart},
  title =	{{Polynomial Termination Over \mathbb{N} Is Undecidable}},
  booktitle =	{7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-233-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{228},
  editor =	{Felty, Amy P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2022.27},
  URN =		{urn:nbn:de:0030-drops-163081},
  doi =		{10.4230/LIPIcs.FSCD.2022.27},
  annote =	{Keywords: Term Rewriting, Polynomial Termination, Undecidability}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail