Time and Space Bounds for Reversible Simulation View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2001-07-04

AUTHORS

Harry Buhrman , John Tromp , Paul Vitányi

ABSTRACT

We prove a general upper bound on the tradeoff between time and space that suffices for the reversible simulation of irreversible computation. Previously, only simulations using exponential time or quadratic space were known. The tradeoff shows for the first time that we can simultaneously achieve subexponential time and subquadratic space. The boundary values are the exponential time with hardly any extra space required by the Lange-McKenzie-Tapp method and the (log 3)th power time with square space required by the Bennett method. We also give the first general lower bound on the extra storage space required by general reversible simulation. This lower bound is optimal in that it is achieved by some reversible simulations. More... »

PAGES

1017-1027

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-42287-7
978-3-540-48224-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48224-5_82

DOI

http://dx.doi.org/10.1007/3-540-48224-5_82

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1016579794


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "CWI, Kruislaan 413, 1098, Amsterdam, SJ, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.6054.7", 
          "name": [
            "CWI, Kruislaan 413, 1098, Amsterdam, SJ, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Buhrman", 
        "givenName": "Harry", 
        "id": "sg:person.0773331206.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0773331206.93"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "CWI, Kruislaan 413, 1098, Amsterdam, SJ, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.6054.7", 
          "name": [
            "CWI, Kruislaan 413, 1098, Amsterdam, SJ, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tromp", 
        "givenName": "John", 
        "id": "sg:person.011226061741.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011226061741.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "CWI, Kruislaan 413, 1098, Amsterdam, SJ, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.6054.7", 
          "name": [
            "CWI, Kruislaan 413, 1098, Amsterdam, SJ, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vit\u00e1nyi", 
        "givenName": "Paul", 
        "id": "sg:person.014213763741.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014213763741.01"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001-07-04", 
    "datePublishedReg": "2001-07-04", 
    "description": "We prove a general upper bound on the tradeoff between time and space that suffices for the reversible simulation of irreversible computation. Previously, only simulations using exponential time or quadratic space were known. The tradeoff shows for the first time that we can simultaneously achieve subexponential time and subquadratic space. The boundary values are the exponential time with hardly any extra space required by the Lange-McKenzie-Tapp method and the (log 3)th power time with square space required by the Bennett method. We also give the first general lower bound on the extra storage space required by general reversible simulation. This lower bound is optimal in that it is achieved by some reversible simulations.", 
    "editor": [
      {
        "familyName": "Orejas", 
        "givenName": "Fernando", 
        "type": "Person"
      }, 
      {
        "familyName": "Spirakis", 
        "givenName": "Paul G.", 
        "type": "Person"
      }, 
      {
        "familyName": "van Leeuwen", 
        "givenName": "Jan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48224-5_82", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42287-7", 
        "978-3-540-48224-6"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "reversible simulation", 
      "exponential time", 
      "boundary values", 
      "general upper", 
      "quadratic space", 
      "subexponential time", 
      "space bounds", 
      "space", 
      "simulations", 
      "irreversible computation", 
      "power time", 
      "tradeoff", 
      "bounds", 
      "storage space", 
      "computation", 
      "upper", 
      "square space", 
      "extra space", 
      "only simulation", 
      "time", 
      "Bennett method", 
      "values", 
      "first time", 
      "log", 
      "extra storage space", 
      "subquadratic space", 
      "method", 
      "Lange-McKenzie", 
      "TAPP method", 
      "general reversible simulation"
    ], 
    "name": "Time and Space Bounds for Reversible Simulation", 
    "pagination": "1017-1027", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1016579794"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48224-5_82"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48224-5_82", 
      "https://app.dimensions.ai/details/publication/pub.1016579794"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:11", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_445.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-48224-5_82"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-48224-5_82'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-48224-5_82'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48224-5_82'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48224-5_82'


 

This table displays all metadata directly associated to this object as RDF triples.

114 TRIPLES      23 PREDICATES      55 URIs      48 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48224-5_82 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N42ba441a97c140f4b3b01c7b8ed3331f
4 schema:datePublished 2001-07-04
5 schema:datePublishedReg 2001-07-04
6 schema:description We prove a general upper bound on the tradeoff between time and space that suffices for the reversible simulation of irreversible computation. Previously, only simulations using exponential time or quadratic space were known. The tradeoff shows for the first time that we can simultaneously achieve subexponential time and subquadratic space. The boundary values are the exponential time with hardly any extra space required by the Lange-McKenzie-Tapp method and the (log 3)th power time with square space required by the Bennett method. We also give the first general lower bound on the extra storage space required by general reversible simulation. This lower bound is optimal in that it is achieved by some reversible simulations.
7 schema:editor N80c681a39bd34f3c90f07fc4b8e2f36a
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nfa3d47ba7fb047028e03b4d5f3a5bacc
12 schema:keywords Bennett method
13 Lange-McKenzie
14 TAPP method
15 boundary values
16 bounds
17 computation
18 exponential time
19 extra space
20 extra storage space
21 first time
22 general reversible simulation
23 general upper
24 irreversible computation
25 log
26 method
27 only simulation
28 power time
29 quadratic space
30 reversible simulation
31 simulations
32 space
33 space bounds
34 square space
35 storage space
36 subexponential time
37 subquadratic space
38 time
39 tradeoff
40 upper
41 values
42 schema:name Time and Space Bounds for Reversible Simulation
43 schema:pagination 1017-1027
44 schema:productId N3d1c088af6ba4cca8e875eddd0ba479e
45 Ndc010070894140e09c1dce0aa6250bda
46 schema:publisher Nf2f15ee917c644e68644e0d2cc323d38
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016579794
48 https://doi.org/10.1007/3-540-48224-5_82
49 schema:sdDatePublished 2021-12-01T20:11
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N3c693a15894945c586c1ba631ed1840a
52 schema:url https://doi.org/10.1007/3-540-48224-5_82
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N0377c9aab4514f26aed6db144b0a303f rdf:first sg:person.014213763741.01
57 rdf:rest rdf:nil
58 N3c693a15894945c586c1ba631ed1840a schema:name Springer Nature - SN SciGraph project
59 rdf:type schema:Organization
60 N3d1c088af6ba4cca8e875eddd0ba479e schema:name doi
61 schema:value 10.1007/3-540-48224-5_82
62 rdf:type schema:PropertyValue
63 N40021c187be54a289b497a3ca5c711fe schema:familyName Orejas
64 schema:givenName Fernando
65 rdf:type schema:Person
66 N42ba441a97c140f4b3b01c7b8ed3331f rdf:first sg:person.0773331206.93
67 rdf:rest N78f5f19488374d9a817dabaa249725c0
68 N4dd8ee9d3bd2463a8956955be0be8f48 schema:familyName Spirakis
69 schema:givenName Paul G.
70 rdf:type schema:Person
71 N78f5f19488374d9a817dabaa249725c0 rdf:first sg:person.011226061741.52
72 rdf:rest N0377c9aab4514f26aed6db144b0a303f
73 N7e15a94e40b94cdeaa32e5ec186e8d62 schema:familyName van Leeuwen
74 schema:givenName Jan
75 rdf:type schema:Person
76 N80c681a39bd34f3c90f07fc4b8e2f36a rdf:first N40021c187be54a289b497a3ca5c711fe
77 rdf:rest Nf2d8b7d768f441d2849f1daf1d83c770
78 Ndc010070894140e09c1dce0aa6250bda schema:name dimensions_id
79 schema:value pub.1016579794
80 rdf:type schema:PropertyValue
81 Nf2d8b7d768f441d2849f1daf1d83c770 rdf:first N4dd8ee9d3bd2463a8956955be0be8f48
82 rdf:rest Nf79ab7d705fa4ee3b2029c8f1d58c0fb
83 Nf2f15ee917c644e68644e0d2cc323d38 schema:name Springer Nature
84 rdf:type schema:Organisation
85 Nf79ab7d705fa4ee3b2029c8f1d58c0fb rdf:first N7e15a94e40b94cdeaa32e5ec186e8d62
86 rdf:rest rdf:nil
87 Nfa3d47ba7fb047028e03b4d5f3a5bacc schema:isbn 978-3-540-42287-7
88 978-3-540-48224-6
89 schema:name Automata, Languages and Programming
90 rdf:type schema:Book
91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information and Computing Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
95 schema:name Artificial Intelligence and Image Processing
96 rdf:type schema:DefinedTerm
97 sg:person.011226061741.52 schema:affiliation grid-institutes:grid.6054.7
98 schema:familyName Tromp
99 schema:givenName John
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011226061741.52
101 rdf:type schema:Person
102 sg:person.014213763741.01 schema:affiliation grid-institutes:grid.6054.7
103 schema:familyName Vitányi
104 schema:givenName Paul
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014213763741.01
106 rdf:type schema:Person
107 sg:person.0773331206.93 schema:affiliation grid-institutes:grid.6054.7
108 schema:familyName Buhrman
109 schema:givenName Harry
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0773331206.93
111 rdf:type schema:Person
112 grid-institutes:grid.6054.7 schema:alternateName CWI, Kruislaan 413, 1098, Amsterdam, SJ, The Netherlands
113 schema:name CWI, Kruislaan 413, 1098, Amsterdam, SJ, The Netherlands
114 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...