Journal article 716 views 48 downloads
Decision problems for linear recurrences involving arbitrary real numbers
Eike Neumann
Logical Methods in Computer Science, Volume: 17, Issue: 3, Pages: 16:1 - 16:26
Swansea University Author: Eike Neumann
-
PDF | Version of Record
© E. Neumann. This work is licensed under the Creative Commons Attribution License
Download (530.38KB)
DOI (Published version): 10.46298/lmcs-17(3:16)2021
Abstract
We study the decidability of the Skolem Problem, the Positivity Problem, and the Ultimate Positivity Problem for linear recurrences with real number initial values and real number coefficients in the bit-model of real computation. We show that for each problem there exists a correct partial algorith...
| Published in: | Logical Methods in Computer Science |
|---|---|
| ISSN: | 1860-5974 |
| Published: |
Centre pour la Communication Scientifique Directe (CCSD)
2021
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa60145 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| first_indexed |
2022-06-07T13:03:23Z |
|---|---|
| last_indexed |
2023-01-11T14:41:55Z |
| id |
cronfa60145 |
| recordtype |
SURis |
| fullrecord |
<?xml version="1.0"?><rfc1807><datestamp>2022-11-07T10:34:17.1571979</datestamp><bib-version>v2</bib-version><id>60145</id><entry>2022-06-07</entry><title>Decision problems for linear recurrences involving arbitrary real numbers</title><swanseaauthors><author><sid>1bf535eaa8d6fcdfbd464a511c1c0c78</sid><firstname>Eike</firstname><surname>Neumann</surname><name>Eike Neumann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2022-06-07</date><deptcode>SCS</deptcode><abstract>We study the decidability of the Skolem Problem, the Positivity Problem, and the Ultimate Positivity Problem for linear recurrences with real number initial values and real number coefficients in the bit-model of real computation. We show that for each problem there exists a correct partial algorithm which halts for all problem instances for which the answer is locally constant, thus establishing that all three problems are as close to decidable as one can expect them to be in this setting. We further show that the algorithms for the Positivity Problem and the Ultimate Positivity Problem halt on almost every instance with respect to the usual Lebesgue measure on Euclidean space. In comparison, the analogous problems for exact rational or real algebraic coefficients are known to be decidable only for linear recurrences of fairly low order.</abstract><type>Journal Article</type><journal>Logical Methods in Computer Science</journal><volume>17</volume><journalNumber>3</journalNumber><paginationStart>16:1</paginationStart><paginationEnd>16:26</paginationEnd><publisher>Centre pour la Communication Scientifique Directe (CCSD)</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic>1860-5974</issnElectronic><keywords>Skolem Problem, Linear Recurrences, Computable Analysis</keywords><publishedDay>10</publishedDay><publishedMonth>8</publishedMonth><publishedYear>2021</publishedYear><publishedDate>2021-08-10</publishedDate><doi>10.46298/lmcs-17(3:16)2021</doi><url/><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><funders/><projectreference/><lastEdited>2022-11-07T10:34:17.1571979</lastEdited><Created>2022-06-07T14:00:52.1329894</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><order>1</order></author></authors><documents><document><filename>60145__24469__3614dae042854386b7074514d9a6ee5c.pdf</filename><originalFilename>60145_VoR.pdf</originalFilename><uploaded>2022-07-07T11:00:48.5532804</uploaded><type>Output</type><contentLength>543110</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>© E. Neumann. This work is licensed under the Creative Commons Attribution License</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>https://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807> |
| spelling |
2022-11-07T10:34:17.1571979 v2 60145 2022-06-07 Decision problems for linear recurrences involving arbitrary real numbers 1bf535eaa8d6fcdfbd464a511c1c0c78 Eike Neumann Eike Neumann true false 2022-06-07 SCS We study the decidability of the Skolem Problem, the Positivity Problem, and the Ultimate Positivity Problem for linear recurrences with real number initial values and real number coefficients in the bit-model of real computation. We show that for each problem there exists a correct partial algorithm which halts for all problem instances for which the answer is locally constant, thus establishing that all three problems are as close to decidable as one can expect them to be in this setting. We further show that the algorithms for the Positivity Problem and the Ultimate Positivity Problem halt on almost every instance with respect to the usual Lebesgue measure on Euclidean space. In comparison, the analogous problems for exact rational or real algebraic coefficients are known to be decidable only for linear recurrences of fairly low order. Journal Article Logical Methods in Computer Science 17 3 16:1 16:26 Centre pour la Communication Scientifique Directe (CCSD) 1860-5974 Skolem Problem, Linear Recurrences, Computable Analysis 10 8 2021 2021-08-10 10.46298/lmcs-17(3:16)2021 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2022-11-07T10:34:17.1571979 2022-06-07T14:00:52.1329894 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Eike Neumann 1 60145__24469__3614dae042854386b7074514d9a6ee5c.pdf 60145_VoR.pdf 2022-07-07T11:00:48.5532804 Output 543110 application/pdf Version of Record true © E. Neumann. This work is licensed under the Creative Commons Attribution License true eng https://creativecommons.org/licenses/by/4.0/ |
| title |
Decision problems for linear recurrences involving arbitrary real numbers |
| spellingShingle |
Decision problems for linear recurrences involving arbitrary real numbers Eike Neumann |
| title_short |
Decision problems for linear recurrences involving arbitrary real numbers |
| title_full |
Decision problems for linear recurrences involving arbitrary real numbers |
| title_fullStr |
Decision problems for linear recurrences involving arbitrary real numbers |
| title_full_unstemmed |
Decision problems for linear recurrences involving arbitrary real numbers |
| title_sort |
Decision problems for linear recurrences involving arbitrary real numbers |
| author_id_str_mv |
1bf535eaa8d6fcdfbd464a511c1c0c78 |
| author_id_fullname_str_mv |
1bf535eaa8d6fcdfbd464a511c1c0c78_***_Eike Neumann |
| author |
Eike Neumann |
| author2 |
Eike Neumann |
| format |
Journal article |
| container_title |
Logical Methods in Computer Science |
| container_volume |
17 |
| container_issue |
3 |
| container_start_page |
16:1 |
| publishDate |
2021 |
| institution |
Swansea University |
| issn |
1860-5974 |
| doi_str_mv |
10.46298/lmcs-17(3:16)2021 |
| publisher |
Centre pour la Communication Scientifique Directe (CCSD) |
| 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 |
1 |
| active_str |
0 |
| description |
We study the decidability of the Skolem Problem, the Positivity Problem, and the Ultimate Positivity Problem for linear recurrences with real number initial values and real number coefficients in the bit-model of real computation. We show that for each problem there exists a correct partial algorithm which halts for all problem instances for which the answer is locally constant, thus establishing that all three problems are as close to decidable as one can expect them to be in this setting. We further show that the algorithms for the Positivity Problem and the Ultimate Positivity Problem halt on almost every instance with respect to the usual Lebesgue measure on Euclidean space. In comparison, the analogous problems for exact rational or real algebraic coefficients are known to be decidable only for linear recurrences of fairly low order. |
| published_date |
2021-08-10T04:18:00Z |
| _version_ |
1763754199996170240 |
| score |
11.035634 |