Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2022.27
URN: urn:nbn:de:0030-drops-163081
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16308/
Mitterwallner, Fabian ; Middeldorp, Aart
Polynomial Termination Over ℕ Is Undecidable
| pdf-format: |
|
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.
BibTeX - Entry
@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/opus/volltexte/2022/16308},
URN = {urn:nbn:de:0030-drops-163081},
doi = {10.4230/LIPIcs.FSCD.2022.27},
annote = {Keywords: Term Rewriting, Polynomial Termination, Undecidability}
}
| Keywords: | Term Rewriting, Polynomial Termination, Undecidability | |
| Seminar: | 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 28.06.2022 |
