Making Programs Reversible with Minimal Extra Data View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2022-07-04

AUTHORS

Robert Glück, Tetsuo Yokoyama

ABSTRACT

Reversible computing is an unconventional computing paradigm that comes with specific challenges. One of the important questions is the existence of reversible programs with minimal extra output (garbage data). To answer this question for programs that implement partial functions over countable domains, we introduce an order on infinite garbage sets and a notion of minimality. To this end, we present two methods for functions specified by decidable and semi-decidable predicates. Both methods are universal, which means they work for all programs specified by the predicates. They cover Bennett’s classic input-erasing reversible computation of injective functions. Hence, any program written in a Turing-complete programming language can be implemented with g-minimal garbage in an r-Turing-complete reversible programming language. This generality comes at the cost of a considerable runtime due to the generate-and-test approach. More... »

PAGES

467-480

References to SciGraph publications

  • 2017. Theory of Reversible Computing in NONE
  • 1980. Reversible computing in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2002-03-01. Program transformation system based on generalized partial computation in NEW GENERATION COMPUTING
  • 1979. Program inversion in PROGRAM CONSTRUCTION
  • 2014. On DNA-Based Gellular Automata in UNCONVENTIONAL COMPUTATION AND NATURAL COMPUTATION
  • 2015-12-09. Programming Techniques for Reversible Comparison Sorts in PROGRAMMING LANGUAGES AND SYSTEMS
  • 2005. The Program Inverter LRinv and Its Structure in PRACTICAL ASPECTS OF DECLARATIVE LANGUAGES
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00354-022-00169-z

    DOI

    http://dx.doi.org/10.1007/s00354-022-00169-z

    DIMENSIONS

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


    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/0803", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computer Software", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "DIKU, Department of Computer Science, University of Copenhagen, 2100, Copenhagen, Denmark", 
              "id": "http://www.grid.ac/institutes/grid.5254.6", 
              "name": [
                "DIKU, Department of Computer Science, University of Copenhagen, 2100, Copenhagen, Denmark"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gl\u00fcck", 
            "givenName": "Robert", 
            "id": "sg:person.010754010217.31", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Electronics and Communication Technology, Nanzan University, 466-8673, Nagoya, Japan", 
              "id": "http://www.grid.ac/institutes/grid.444385.a", 
              "name": [
                "Department of Electronics and Communication Technology, Nanzan University, 466-8673, Nagoya, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yokoyama", 
            "givenName": "Tetsuo", 
            "id": "sg:person.015342016423.59", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015342016423.59"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-4-431-56606-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1092569664", 
              "https://doi.org/10.1007/978-4-431-56606-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf03037260", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000035698", 
              "https://doi.org/10.1007/bf03037260"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-10003-2_104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006731052", 
              "https://doi.org/10.1007/3-540-10003-2_104"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-26529-2_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021275775", 
              "https://doi.org/10.1007/978-3-319-26529-2_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-08123-6_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045958408", 
              "https://doi.org/10.1007/978-3-319-08123-6_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30557-6_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000695046", 
              "https://doi.org/10.1007/978-3-540-30557-6_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0014657", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017699924", 
              "https://doi.org/10.1007/bfb0014657"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-07-04", 
        "datePublishedReg": "2022-07-04", 
        "description": "Reversible computing is an unconventional computing paradigm that comes with specific challenges. One of the important questions is the existence of reversible programs with minimal extra output (garbage data). To answer this question for programs that implement partial functions over countable domains, we introduce an order on infinite garbage sets and a notion of minimality. To this end, we present two methods for functions specified by decidable and semi-decidable predicates. Both methods are universal, which means they work for all programs specified by the predicates. They cover Bennett\u2019s classic input-erasing reversible computation of injective functions. Hence, any program written in a Turing-complete programming language can be implemented with g-minimal garbage in an r-Turing-complete reversible programming language. This generality comes at the cost of a considerable runtime due to the generate-and-test approach.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00354-022-00169-z", 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.7538080", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1053619", 
            "issn": [
              "0288-3635", 
              "1882-7055"
            ], 
            "name": "New Generation Computing", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "40"
          }
        ], 
        "keywords": [
          "programming language", 
          "Turing-complete programming language", 
          "unconventional computing paradigms", 
          "computing paradigm", 
          "reversible programming languages", 
          "considerable runtime", 
          "countable domain", 
          "extra data", 
          "reversible computation", 
          "reversible computing", 
          "reversible programs", 
          "notion of minimality", 
          "predicates", 
          "injective function", 
          "test approach", 
          "language", 
          "computing", 
          "specific challenges", 
          "runtime", 
          "partial functions", 
          "computation", 
          "paradigm", 
          "set", 
          "extra output", 
          "generality", 
          "method", 
          "challenges", 
          "cost", 
          "program", 
          "domain", 
          "generate", 
          "garbage", 
          "minimality", 
          "output", 
          "data", 
          "order", 
          "notion", 
          "function", 
          "important questions", 
          "end", 
          "questions", 
          "existence", 
          "approach"
        ], 
        "name": "Making Programs Reversible with Minimal Extra Data", 
        "pagination": "467-480", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1149205972"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00354-022-00169-z"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00354-022-00169-z", 
          "https://app.dimensions.ai/details/publication/pub.1149205972"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-11-24T21:09", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_942.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00354-022-00169-z"
      }
    ]
     

    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/s00354-022-00169-z'

    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/s00354-022-00169-z'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00354-022-00169-z'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00354-022-00169-z'


     

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

    140 TRIPLES      21 PREDICATES      74 URIs      59 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00354-022-00169-z schema:about anzsrc-for:08
    2 anzsrc-for:0803
    3 schema:author N45d8c52ebed14cb3863837de917b557c
    4 schema:citation sg:pub.10.1007/3-540-10003-2_104
    5 sg:pub.10.1007/978-3-319-08123-6_15
    6 sg:pub.10.1007/978-3-319-26529-2_22
    7 sg:pub.10.1007/978-3-540-30557-6_17
    8 sg:pub.10.1007/978-4-431-56606-9
    9 sg:pub.10.1007/bf03037260
    10 sg:pub.10.1007/bfb0014657
    11 schema:datePublished 2022-07-04
    12 schema:datePublishedReg 2022-07-04
    13 schema:description Reversible computing is an unconventional computing paradigm that comes with specific challenges. One of the important questions is the existence of reversible programs with minimal extra output (garbage data). To answer this question for programs that implement partial functions over countable domains, we introduce an order on infinite garbage sets and a notion of minimality. To this end, we present two methods for functions specified by decidable and semi-decidable predicates. Both methods are universal, which means they work for all programs specified by the predicates. They cover Bennett’s classic input-erasing reversible computation of injective functions. Hence, any program written in a Turing-complete programming language can be implemented with g-minimal garbage in an r-Turing-complete reversible programming language. This generality comes at the cost of a considerable runtime due to the generate-and-test approach.
    14 schema:genre article
    15 schema:isAccessibleForFree false
    16 schema:isPartOf N7fce29b3b1534d4bb74500715b838821
    17 N9defac87df4a4f49802b5b4355fbea67
    18 sg:journal.1053619
    19 schema:keywords Turing-complete programming language
    20 approach
    21 challenges
    22 computation
    23 computing
    24 computing paradigm
    25 considerable runtime
    26 cost
    27 countable domain
    28 data
    29 domain
    30 end
    31 existence
    32 extra data
    33 extra output
    34 function
    35 garbage
    36 generality
    37 generate
    38 important questions
    39 injective function
    40 language
    41 method
    42 minimality
    43 notion
    44 notion of minimality
    45 order
    46 output
    47 paradigm
    48 partial functions
    49 predicates
    50 program
    51 programming language
    52 questions
    53 reversible computation
    54 reversible computing
    55 reversible programming languages
    56 reversible programs
    57 runtime
    58 set
    59 specific challenges
    60 test approach
    61 unconventional computing paradigms
    62 schema:name Making Programs Reversible with Minimal Extra Data
    63 schema:pagination 467-480
    64 schema:productId N205028e465cf463ea19df5b0c341ce56
    65 Nb012afb87c3f44d4a60160b1b73d7336
    66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1149205972
    67 https://doi.org/10.1007/s00354-022-00169-z
    68 schema:sdDatePublished 2022-11-24T21:09
    69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    70 schema:sdPublisher Naa2b7fb10a1f4ef798a183b366b3c2d2
    71 schema:url https://doi.org/10.1007/s00354-022-00169-z
    72 sgo:license sg:explorer/license/
    73 sgo:sdDataset articles
    74 rdf:type schema:ScholarlyArticle
    75 N205028e465cf463ea19df5b0c341ce56 schema:name doi
    76 schema:value 10.1007/s00354-022-00169-z
    77 rdf:type schema:PropertyValue
    78 N45d8c52ebed14cb3863837de917b557c rdf:first sg:person.010754010217.31
    79 rdf:rest Ncccb7e5334b347b6b8ff7c48860ea124
    80 N7fce29b3b1534d4bb74500715b838821 schema:volumeNumber 40
    81 rdf:type schema:PublicationVolume
    82 N9defac87df4a4f49802b5b4355fbea67 schema:issueNumber 2
    83 rdf:type schema:PublicationIssue
    84 Naa2b7fb10a1f4ef798a183b366b3c2d2 schema:name Springer Nature - SN SciGraph project
    85 rdf:type schema:Organization
    86 Nb012afb87c3f44d4a60160b1b73d7336 schema:name dimensions_id
    87 schema:value pub.1149205972
    88 rdf:type schema:PropertyValue
    89 Ncccb7e5334b347b6b8ff7c48860ea124 rdf:first sg:person.015342016423.59
    90 rdf:rest rdf:nil
    91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Information and Computing Sciences
    93 rdf:type schema:DefinedTerm
    94 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
    95 schema:name Computer Software
    96 rdf:type schema:DefinedTerm
    97 sg:grant.7538080 http://pending.schema.org/fundedItem sg:pub.10.1007/s00354-022-00169-z
    98 rdf:type schema:MonetaryGrant
    99 sg:journal.1053619 schema:issn 0288-3635
    100 1882-7055
    101 schema:name New Generation Computing
    102 schema:publisher Springer Nature
    103 rdf:type schema:Periodical
    104 sg:person.010754010217.31 schema:affiliation grid-institutes:grid.5254.6
    105 schema:familyName Glück
    106 schema:givenName Robert
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    108 rdf:type schema:Person
    109 sg:person.015342016423.59 schema:affiliation grid-institutes:grid.444385.a
    110 schema:familyName Yokoyama
    111 schema:givenName Tetsuo
    112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015342016423.59
    113 rdf:type schema:Person
    114 sg:pub.10.1007/3-540-10003-2_104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006731052
    115 https://doi.org/10.1007/3-540-10003-2_104
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/978-3-319-08123-6_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045958408
    118 https://doi.org/10.1007/978-3-319-08123-6_15
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/978-3-319-26529-2_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021275775
    121 https://doi.org/10.1007/978-3-319-26529-2_22
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/978-3-540-30557-6_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000695046
    124 https://doi.org/10.1007/978-3-540-30557-6_17
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/978-4-431-56606-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092569664
    127 https://doi.org/10.1007/978-4-431-56606-9
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/bf03037260 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000035698
    130 https://doi.org/10.1007/bf03037260
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/bfb0014657 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017699924
    133 https://doi.org/10.1007/bfb0014657
    134 rdf:type schema:CreativeWork
    135 grid-institutes:grid.444385.a schema:alternateName Department of Electronics and Communication Technology, Nanzan University, 466-8673, Nagoya, Japan
    136 schema:name Department of Electronics and Communication Technology, Nanzan University, 466-8673, Nagoya, Japan
    137 rdf:type schema:Organization
    138 grid-institutes:grid.5254.6 schema:alternateName DIKU, Department of Computer Science, University of Copenhagen, 2100, Copenhagen, Denmark
    139 schema:name DIKU, Department of Computer Science, University of Copenhagen, 2100, Copenhagen, Denmark
    140 rdf:type schema:Organization
     




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


    ...