Termination of Real Linear Loops
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914525904633856 |
|---|---|
| author | Neumann, Eike Tembo, Margret |
| author_facet | Neumann, Eike Tembo, Margret |
| contents | We study the problem of deciding universal termination of linear and affine loops over the reals in the bit-model of real computation. We show that both problems are as close to decidable as one can expect them to be: there exist sound partial algorithms that halt on all problem instances whose answer is robust under all sufficiently small perturbations. We further show that in each case the set of non-robust problem instances has Lebesgue measure zero. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_00947 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Termination of Real Linear Loops Neumann, Eike Tembo, Margret Computational Complexity Logic in Computer Science We study the problem of deciding universal termination of linear and affine loops over the reals in the bit-model of real computation. We show that both problems are as close to decidable as one can expect them to be: there exist sound partial algorithms that halt on all problem instances whose answer is robust under all sufficiently small perturbations. We further show that in each case the set of non-robust problem instances has Lebesgue measure zero. |
| title | Termination of Real Linear Loops |
| topic | Computational Complexity Logic in Computer Science |
| url | https://arxiv.org/abs/2605.00947 |