Book chapter 235 views
On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions
Eike Neumann
Lecture Notes in Computer Science, Volume: (LNCS,volume 14235), Pages: 98 - 112
Swansea University Author: Eike Neumann
Full text not available from this repository: check for access using links below.
DOI (Published version): 10.1007/978-3-031-45286-4_8
Abstract
We study the computational complexity of a robust version of the problem of testing two univariate C-finite functions for eventual inequality at large times. Specifically, working in the bit-model of real computation, we consider the eventual inequality testing problem for real functions that are sp...
Published in: | Lecture Notes in Computer Science |
---|---|
ISBN: | 9783031452857 9783031452864 |
ISSN: | 0302-9743 1611-3349 |
Published: |
Cham
Springer Nature Switzerland
2023
|
Online Access: |
Check full text
|
URI: | https://cronfa.swan.ac.uk/Record/cronfa64077 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
first_indexed |
2023-08-15T11:57:12Z |
---|---|
last_indexed |
2023-08-15T11:57:12Z |
id |
cronfa64077 |
recordtype |
SURis |
fullrecord |
<?xml version="1.0" encoding="utf-8"?><rfc1807 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema"><bib-version>v2</bib-version><id>64077</id><entry>2023-08-15</entry><title>On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions</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>2023-08-15</date><deptcode>SCS</deptcode><abstract>We study the computational complexity of a robust version of the problem of testing two univariate C-finite functions for eventual inequality at large times. Specifically, working in the bit-model of real computation, we consider the eventual inequality testing problem for real functions that are specified by homogeneous linear Cauchy problems with arbitrary real coefficients and initial values. In order to assign to this problem a well-defined computational complexity, we develop a natural notion of polynomial-time decidability of subsets of computable metric spaces which extends our recently introduced notion of maximal partial decidability. We show that eventual inequality of C-finite functions is polynomial-time decidable in this sense.</abstract><type>Book chapter</type><journal>Lecture Notes in Computer Science</journal><volume>(LNCS,volume 14235)</volume><journalNumber/><paginationStart>98</paginationStart><paginationEnd>112</paginationEnd><publisher>Springer Nature Switzerland</publisher><placeOfPublication>Cham</placeOfPublication><isbnPrint>9783031452857</isbnPrint><isbnElectronic>9783031452864</isbnElectronic><issnPrint>0302-9743</issnPrint><issnElectronic>1611-3349</issnElectronic><keywords/><publishedDay>5</publishedDay><publishedMonth>10</publishedMonth><publishedYear>2023</publishedYear><publishedDate>2023-10-05</publishedDate><doi>10.1007/978-3-031-45286-4_8</doi><url>http://dx.doi.org/10.1007/978-3-031-45286-4_8</url><notes>Part of Book Series: Lecture Notes in Computer Science (LNCS, volume 14235)</notes><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><funders/><projectreference/><lastEdited>2023-10-23T17:47:19.7826968</lastEdited><Created>2023-08-15T11:00:32.5767074</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/><OutputDurs/></rfc1807> |
spelling |
v2 64077 2023-08-15 On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions 1bf535eaa8d6fcdfbd464a511c1c0c78 Eike Neumann Eike Neumann true false 2023-08-15 SCS We study the computational complexity of a robust version of the problem of testing two univariate C-finite functions for eventual inequality at large times. Specifically, working in the bit-model of real computation, we consider the eventual inequality testing problem for real functions that are specified by homogeneous linear Cauchy problems with arbitrary real coefficients and initial values. In order to assign to this problem a well-defined computational complexity, we develop a natural notion of polynomial-time decidability of subsets of computable metric spaces which extends our recently introduced notion of maximal partial decidability. We show that eventual inequality of C-finite functions is polynomial-time decidable in this sense. Book chapter Lecture Notes in Computer Science (LNCS,volume 14235) 98 112 Springer Nature Switzerland Cham 9783031452857 9783031452864 0302-9743 1611-3349 5 10 2023 2023-10-05 10.1007/978-3-031-45286-4_8 http://dx.doi.org/10.1007/978-3-031-45286-4_8 Part of Book Series: Lecture Notes in Computer Science (LNCS, volume 14235) COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2023-10-23T17:47:19.7826968 2023-08-15T11:00:32.5767074 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Eike Neumann 1 |
title |
On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions |
spellingShingle |
On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions Eike Neumann |
title_short |
On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions |
title_full |
On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions |
title_fullStr |
On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions |
title_full_unstemmed |
On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions |
title_sort |
On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions |
author_id_str_mv |
1bf535eaa8d6fcdfbd464a511c1c0c78 |
author_id_fullname_str_mv |
1bf535eaa8d6fcdfbd464a511c1c0c78_***_Eike Neumann |
author |
Eike Neumann |
author2 |
Eike Neumann |
format |
Book chapter |
container_title |
Lecture Notes in Computer Science |
container_volume |
(LNCS,volume 14235) |
container_start_page |
98 |
publishDate |
2023 |
institution |
Swansea University |
isbn |
9783031452857 9783031452864 |
issn |
0302-9743 1611-3349 |
doi_str_mv |
10.1007/978-3-031-45286-4_8 |
publisher |
Springer Nature Switzerland |
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 |
url |
http://dx.doi.org/10.1007/978-3-031-45286-4_8 |
document_store_str |
0 |
active_str |
0 |
description |
We study the computational complexity of a robust version of the problem of testing two univariate C-finite functions for eventual inequality at large times. Specifically, working in the bit-model of real computation, we consider the eventual inequality testing problem for real functions that are specified by homogeneous linear Cauchy problems with arbitrary real coefficients and initial values. In order to assign to this problem a well-defined computational complexity, we develop a natural notion of polynomial-time decidability of subsets of computable metric spaces which extends our recently introduced notion of maximal partial decidability. We show that eventual inequality of C-finite functions is polynomial-time decidable in this sense. |
published_date |
2023-10-05T17:47:21Z |
_version_ |
1780565557849882624 |
score |
11.021648 |