No Cover Image

Book chapter 182 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.

Check full text

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...

Full description

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.013799

Similar Items