No Cover Image

Conference Paper/Proceeding/Abstract 11 views

Termination of Real Linear Loops

Eike Neumann Orcid Logo, Margret Tembo

Lecture Notes in Computer Science

Swansea University Authors: Eike Neumann Orcid Logo, Margret Tembo

Abstract

We study the problem of deciding universal termination of linear and 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...

Full description

Published in: Lecture Notes in Computer Science
Published: Springer
URI: https://cronfa.swan.ac.uk/Record/cronfa72063
first_indexed 2026-06-11T12:33:05Z
last_indexed 2026-06-12T13:21:37Z
id cronfa72063
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2026-06-11T13:33:03.8316738</datestamp><bib-version>v2</bib-version><id>72063</id><entry>2026-06-11</entry><title>Termination of Real Linear Loops</title><swanseaauthors><author><sid>1bf535eaa8d6fcdfbd464a511c1c0c78</sid><ORCID>0009-0003-2907-1566</ORCID><firstname>Eike</firstname><surname>Neumann</surname><name>Eike Neumann</name><active>true</active><ethesisStudent>false</ethesisStudent></author><author><sid>3d2a31670b964c2081c07ee7213cf933</sid><ORCID/><firstname>Margret</firstname><surname>Tembo</surname><name>Margret Tembo</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2026-06-11</date><deptcode>MACS</deptcode><abstract>We study the problem of deciding universal termination of linear and 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.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>Lecture Notes in Computer Science</journal><volume/><journalNumber/><paginationStart/><paginationEnd/><publisher>Springer</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic/><keywords/><publishedDay>0</publishedDay><publishedMonth>0</publishedMonth><publishedYear>0</publishedYear><publishedDate>0001-01-01</publishedDate><doi/><url/><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm>Not Required</apcterm><funders/><projectreference/><lastEdited>2026-06-11T13:33:03.8316738</lastEdited><Created>2026-06-11T13:27:38.6481148</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Eike</firstname><surname>Neumann</surname><orcid>0009-0003-2907-1566</orcid><order>1</order></author><author><firstname>Margret</firstname><surname>Tembo</surname><orcid/><order>2</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2026-06-11T13:33:03.8316738 v2 72063 2026-06-11 Termination of Real Linear Loops 1bf535eaa8d6fcdfbd464a511c1c0c78 0009-0003-2907-1566 Eike Neumann Eike Neumann true false 3d2a31670b964c2081c07ee7213cf933 Margret Tembo Margret Tembo true false 2026-06-11 MACS We study the problem of deciding universal termination of linear and 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. Conference Paper/Proceeding/Abstract Lecture Notes in Computer Science Springer 0 0 0 0001-01-01 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University Not Required 2026-06-11T13:33:03.8316738 2026-06-11T13:27:38.6481148 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Eike Neumann 0009-0003-2907-1566 1 Margret Tembo 2
title Termination of Real Linear Loops
spellingShingle Termination of Real Linear Loops
Eike Neumann
Margret Tembo
title_short Termination of Real Linear Loops
title_full Termination of Real Linear Loops
title_fullStr Termination of Real Linear Loops
title_full_unstemmed Termination of Real Linear Loops
title_sort Termination of Real Linear Loops
author_id_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78
3d2a31670b964c2081c07ee7213cf933
author_id_fullname_str_mv 1bf535eaa8d6fcdfbd464a511c1c0c78_***_Eike Neumann
3d2a31670b964c2081c07ee7213cf933_***_Margret Tembo
author Eike Neumann
Margret Tembo
author2 Eike Neumann
Margret Tembo
format Conference Paper/Proceeding/Abstract
container_title Lecture Notes in Computer Science
institution Swansea University
publisher Springer
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 0
active_str 0
description We study the problem of deciding universal termination of linear and 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.
published_date 0001-01-01T06:40:47Z
_version_ 1868040291437510656
score 11.0103655

Similar Items