Second-order linear-time computability with applications to computable analysis

Akitoshi Kawamura; Florian Steinberg; Holger Thies

doi:10.1007/978-3-030-14812-6_21

Second-order linear-time computability with applications to computable analysis

Akitoshi Kawamura, Florian Steinberg, Holger Thies

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In this work we put forward a complexity class of type-two linear-time. For such a definition to be meaningful, a detailed protocol for the cost of interactions with functional inputs has to be fixed. This includes some design decisions the defined class is sensible to and we carefully discuss our choices and their implications. We further discuss some properties and examples of operators that are and are not computable in linear-time and nearly linear-time and some applications to computable analysis.

Original language	English
Title of host publication	Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings
Editors	Junzo Watada, T. V. Gopal
Publisher	Springer Verlag
Pages	337-358
Number of pages	22
ISBN (Print)	9783030148119
DOIs	https://doi.org/10.1007/978-3-030-14812-6_21
Publication status	Published - 2019
Event	15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 - Kitakyushu, Japan Duration: Apr 13 2019 → Apr 16 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11436 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019
Country/Territory	Japan
City	Kitakyushu
Period	4/13/19 → 4/16/19

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-030-14812-6_21

Cite this

Kawamura, A., Steinberg, F., & Thies, H. (2019). Second-order linear-time computability with applications to computable analysis. In J. Watada, & T. V. Gopal (Eds.), Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings (pp. 337-358). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11436 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-14812-6_21

Second-order linear-time computability with applications to computable analysis. / Kawamura, Akitoshi; Steinberg, Florian; Thies, Holger.
Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. ed. / Junzo Watada; T. V. Gopal. Springer Verlag, 2019. p. 337-358 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11436 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kawamura, A, Steinberg, F & Thies, H 2019, Second-order linear-time computability with applications to computable analysis. in J Watada & TV Gopal (eds), Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11436 LNCS, Springer Verlag, pp. 337-358, 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019, Kitakyushu, Japan, 4/13/19. https://doi.org/10.1007/978-3-030-14812-6_21

Kawamura A, Steinberg F, Thies H. Second-order linear-time computability with applications to computable analysis. In Watada J, Gopal TV, editors, Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. Springer Verlag. 2019. p. 337-358. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-14812-6_21

Kawamura, Akitoshi ; Steinberg, Florian ; Thies, Holger. / Second-order linear-time computability with applications to computable analysis. Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. editor / Junzo Watada ; T. V. Gopal. Springer Verlag, 2019. pp. 337-358 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{310cf94b0c504379a136d780d5c4fd62,

title = "Second-order linear-time computability with applications to computable analysis",

abstract = "In this work we put forward a complexity class of type-two linear-time. For such a definition to be meaningful, a detailed protocol for the cost of interactions with functional inputs has to be fixed. This includes some design decisions the defined class is sensible to and we carefully discuss our choices and their implications. We further discuss some properties and examples of operators that are and are not computable in linear-time and nearly linear-time and some applications to computable analysis.",

author = "Akitoshi Kawamura and Florian Steinberg and Holger Thies",

note = "Funding Information: Acknowledgements. This work was supported by JSPS KAKENHI Grant Numbers JP18H03203 and JP18J10407, by the Japan Society for the Promotion of Science (JSPS), Core-to-Core Program (A. Advanced Research Networks), by the ANR project FastRelax (ANR-14-CE25-0018-01) of the French National Agency for Research and by EU-MSCA-RISE project 731143 “Computing with Infinite Data” (CID).; 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 ; Conference date: 13-04-2019 Through 16-04-2019",

year = "2019",

doi = "10.1007/978-3-030-14812-6_21",

language = "English",

isbn = "9783030148119",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "337--358",

editor = "Junzo Watada and Gopal, {T. V.}",

booktitle = "Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Second-order linear-time computability with applications to computable analysis

AU - Kawamura, Akitoshi

AU - Steinberg, Florian

AU - Thies, Holger

N1 - Funding Information: Acknowledgements. This work was supported by JSPS KAKENHI Grant Numbers JP18H03203 and JP18J10407, by the Japan Society for the Promotion of Science (JSPS), Core-to-Core Program (A. Advanced Research Networks), by the ANR project FastRelax (ANR-14-CE25-0018-01) of the French National Agency for Research and by EU-MSCA-RISE project 731143 “Computing with Infinite Data” (CID).

PY - 2019

Y1 - 2019

N2 - In this work we put forward a complexity class of type-two linear-time. For such a definition to be meaningful, a detailed protocol for the cost of interactions with functional inputs has to be fixed. This includes some design decisions the defined class is sensible to and we carefully discuss our choices and their implications. We further discuss some properties and examples of operators that are and are not computable in linear-time and nearly linear-time and some applications to computable analysis.

AB - In this work we put forward a complexity class of type-two linear-time. For such a definition to be meaningful, a detailed protocol for the cost of interactions with functional inputs has to be fixed. This includes some design decisions the defined class is sensible to and we carefully discuss our choices and their implications. We further discuss some properties and examples of operators that are and are not computable in linear-time and nearly linear-time and some applications to computable analysis.

UR - http://www.scopus.com/inward/record.url?scp=85064868996&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85064868996&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-14812-6_21

DO - 10.1007/978-3-030-14812-6_21

M3 - Conference contribution

AN - SCOPUS:85064868996

SN - 9783030148119

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 337

EP - 358

BT - Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings

A2 - Watada, Junzo

A2 - Gopal, T. V.

PB - Springer Verlag

T2 - 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019

Y2 - 13 April 2019 through 16 April 2019

ER -

Second-order linear-time computability with applications to computable analysis

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this