About: On the Complexity of Conversion Between Classic Real Number Representations

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: On the Complexity of Conversion Between Classic Real Number Representations Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	On the Complexity of Conversion Between Classic Real Number Representations
Creator	Kristiansen, Lars Simonsen, Jakob
Source	PMC
abstract	It is known that while it is possible to convert between many different representations of irrational numbers (e.g., between Dedekind cuts and Cauchy sequences), it is in general not possible to do so subrecursively: conversions in general need to perform unbounded search. This raises the question of categorizing the pairs of representations between which either subrecursive conversion is possible, or is not possible. The purpose of this paper is to prove the following positive result: for a number of well-known representations (Beatty sequences, Dedekind cuts, General base expansions, Hurwitz characteristics, and Locators) conversion between the representations can be performed effectively and with good subrecursive bounds.
has issue date	2020-06-24(xsd:dateTime)
bibo:doi	10.1007/978-3-030-51466-2_7
has license	no-cc
sha1sum (hex)	e37950188e2bb214ca858e7372bdb6eeac0a4af4
schema:url	https://doi.org/10.1007/978-3-030-51466-2_7
resource representing a document's title	On the Complexity of Conversion Between Classic Real Number Representations
has PubMed Central identifier	PMC7309495
schema:publication	Beyond the Horizon of Computability
resource representing a document's body	covid:e37950188e2bb214ca858e7372bdb6eeac0a4af4#body_text
is schema:about of	named entity 'sequences' named entity 'Complexity' named entity 'DIFFERENT' named entity 'general' named entity 'unbounded search' named entity 'Cauchy sequences' named entity 'Hurwitz' named entity 'original machines' named entity 'polynomial' named entity 'oracle tape' named entity 'oracle' named entity 'Dedekind cuts' named entity 'real numbers' named entity 'binary representations' named entity 'integer' named entity 'rational number' named entity 'oracle tape' named entity 'input size' named entity 'binary search' named entity 'continued fractions' named entity 'closure properties' named entity 'denominator' named entity 'upper bounds' named entity 'continued fractions' named entity 'primitive recursive' named entity 'rationals' named entity 'polynomial time' named entity 'positive integer' named entity 'base-b' named entity 'oracle tape' named entity 'Turing machines' named entity 'Dedekind cut' named entity 'binary representation' named entity 'base-b' named entity 'upper bounds' named entity 'oracle Turing machine' named entity 'irrational number' named entity 'oracle Turing machine' named entity 'Dedekind cuts' named entity 'Cauchy sequences' named entity 'oracle machine' named entity 'Dedekind cut' named entity 'oracle machine' named entity 'oracle' named entity 'non-decreasing' named entity 'unbounded search' named entity 'binary representations' named entity 'Strictly speaking' named entity 'polynomial' named entity 'positive integer' named entity 'base-b' named entity 'mutatis mutandis' named entity 'oracle' named entity 'oracle tape' named entity 'sufficiently large' named entity 'irrational numbers' named entity 'Dedekind cut' named entity 'Beatty sequence' named entity 'Stern-Brocot tree' named entity 'transition relation' named entity 'base-b' named entity 'Bernard Bolzano' named entity 'oracle tape' named entity 'finite set' named entity 'polynomial' named entity 'strictly increasing' named entity 'integer' named entity 'binary representations' named entity 'Hurwitz' named entity 'primitive recursive' named entity 'Farey sequence' named entity 'trace function' named entity 'rationals' named entity 'Hurwitz' named entity 'integer' named entity 'computability' named entity 'computable reals' named entity 'lowest terms' named entity 'Dedekind cuts' named entity 'oracle' named entity 'Stern-Brocot tree' named entity 'oracle machine'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software