Reversible Flowchart Languages and the Structured Reversible Program Theorem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2008

AUTHORS

Tetsuo Yokoyama , Holger Bock Axelsen , Robert Glück

ABSTRACT

Many irreversible computation models have reversible counterparts, but these are poorly understood at present. We introduce reversible flowcharts with an assertion operator and show that any reversible flowchart can be simulated by a structured reversible flowchart using only three control flow operators. Reversible flowcharts are r- Turing-complete, meaning that they can simuluate reversible Turing machines without garbage data. We also demonstrate the injectivization of classical flowcharts into reversible flowcharts. The reversible flowchart computation model provides a theoretical justification for low-level machine code for reversible microprocessors as well as high-level block-structured reversible languages. We give examples for both such languages and illustrate them with a lossless encoder for permutations given by Dijkstra. More... »

PAGES

258-270

References to SciGraph publications

  • 1999. An Introduction to Online and Offline Partial Evaluation Using a Simple Flowchart Language in PARTIAL EVALUATION
  • 2007. A Universal Reversible Turing Machine in MACHINES, COMPUTATIONS, AND UNIVERSALITY
  • 1981. The Science of Programming in NONE
  • 2007. Reversible Machine Code and Its Abstract Processor Architecture in COMPUTER SCIENCE – THEORY AND APPLICATIONS
  • Book

    TITLE

    Automata, Languages and Programming

    ISBN

    978-3-540-70582-6
    978-3-540-70583-3

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-70583-3_22

    DOI

    http://dx.doi.org/10.1007/978-3-540-70583-3_22

    DIMENSIONS

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


    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/2004", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Linguistics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/20", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Language, Communication and Culture", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Nagoya University", 
              "id": "https://www.grid.ac/institutes/grid.27476.30", 
              "name": [
                "NCES, Graduate School of Information Science, Nagoya University,"
              ], 
              "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"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Copenhagen", 
              "id": "https://www.grid.ac/institutes/grid.5254.6", 
              "name": [
                "DIKU, Department of Computer Science, University of Copenhagen,"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Axelsen", 
            "givenName": "Holger Bock", 
            "id": "sg:person.015546427711.73", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015546427711.73"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Copenhagen", 
              "id": "https://www.grid.ac/institutes/grid.5254.6", 
              "name": [
                "DIKU, Department of Computer Science, University of Copenhagen,"
              ], 
              "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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-540-74593-8_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002680503", 
              "https://doi.org/10.1007/978-3-540-74593-8_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74593-8_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002680503", 
              "https://doi.org/10.1007/978-3-540-74593-8_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1062261.1062270", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003907110"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1244381.1244404", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006492707"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-47018-2_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013466468", 
              "https://doi.org/10.1007/3-540-47018-2_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/363534.363539", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014922077"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74510-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015349256", 
              "https://doi.org/10.1007/978-3-540-74510-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74510-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015349256", 
              "https://doi.org/10.1007/978-3-540-74510-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1366230.1366239", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018780610"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1284621.1284643", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021371811"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-5983-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045860299", 
              "https://doi.org/10.1007/978-1-4612-5983-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-5983-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045860299", 
              "https://doi.org/10.1007/978-1-4612-5983-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(77)80007-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046362897"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/355592.365646", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053696262"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0218053", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842152"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0403020", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062844611"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1147/rd.176.0525", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063180324"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2008", 
        "datePublishedReg": "2008-01-01", 
        "description": "Many irreversible computation models have reversible counterparts, but these are poorly understood at present. We introduce reversible flowcharts with an assertion operator and show that any reversible flowchart can be simulated by a structured reversible flowchart using only three control flow operators. Reversible flowcharts are r- Turing-complete, meaning that they can simuluate reversible Turing machines without garbage data. We also demonstrate the injectivization of classical flowcharts into reversible flowcharts. The reversible flowchart computation model provides a theoretical justification for low-level machine code for reversible microprocessors as well as high-level block-structured reversible languages. We give examples for both such languages and illustrate them with a lossless encoder for permutations given by Dijkstra.", 
        "editor": [
          {
            "familyName": "Aceto", 
            "givenName": "Luca", 
            "type": "Person"
          }, 
          {
            "familyName": "Damg\u00e5rd", 
            "givenName": "Ivan", 
            "type": "Person"
          }, 
          {
            "familyName": "Goldberg", 
            "givenName": "Leslie Ann", 
            "type": "Person"
          }, 
          {
            "familyName": "Halld\u00f3rsson", 
            "givenName": "Magn\u00fas M.", 
            "type": "Person"
          }, 
          {
            "familyName": "Ing\u00f3lfsd\u00f3ttir", 
            "givenName": "Anna", 
            "type": "Person"
          }, 
          {
            "familyName": "Walukiewicz", 
            "givenName": "Igor", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-70583-3_22", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-70582-6", 
            "978-3-540-70583-3"
          ], 
          "name": "Automata, Languages and Programming", 
          "type": "Book"
        }, 
        "name": "Reversible Flowchart Languages and the Structured Reversible Program Theorem", 
        "pagination": "258-270", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-70583-3_22"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "6c1fb7a768d4a6835c86170dd3aacbc159ec6eeb2de665cf8c567713b83d4542"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1022695518"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-70583-3_22", 
          "https://app.dimensions.ai/details/publication/pub.1022695518"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T18:10", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8681_00000257.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-540-70583-3_22"
      }
    ]
     

    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/978-3-540-70583-3_22'

    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/978-3-540-70583-3_22'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70583-3_22'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70583-3_22'


     

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

    153 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-70583-3_22 schema:about anzsrc-for:20
    2 anzsrc-for:2004
    3 schema:author N19d2123f8edc4ec8b6c4ff96143d69cf
    4 schema:citation sg:pub.10.1007/3-540-47018-2_2
    5 sg:pub.10.1007/978-1-4612-5983-1
    6 sg:pub.10.1007/978-3-540-74510-5_9
    7 sg:pub.10.1007/978-3-540-74593-8_8
    8 https://doi.org/10.1016/s0022-0000(77)80007-x
    9 https://doi.org/10.1137/0218053
    10 https://doi.org/10.1137/0403020
    11 https://doi.org/10.1145/1062261.1062270
    12 https://doi.org/10.1145/1244381.1244404
    13 https://doi.org/10.1145/1284621.1284643
    14 https://doi.org/10.1145/1366230.1366239
    15 https://doi.org/10.1145/355592.365646
    16 https://doi.org/10.1145/363534.363539
    17 https://doi.org/10.1147/rd.176.0525
    18 schema:datePublished 2008
    19 schema:datePublishedReg 2008-01-01
    20 schema:description Many irreversible computation models have reversible counterparts, but these are poorly understood at present. We introduce reversible flowcharts with an assertion operator and show that any reversible flowchart can be simulated by a structured reversible flowchart using only three control flow operators. Reversible flowcharts are r- Turing-complete, meaning that they can simuluate reversible Turing machines without garbage data. We also demonstrate the injectivization of classical flowcharts into reversible flowcharts. The reversible flowchart computation model provides a theoretical justification for low-level machine code for reversible microprocessors as well as high-level block-structured reversible languages. We give examples for both such languages and illustrate them with a lossless encoder for permutations given by Dijkstra.
    21 schema:editor N151e9a54bca5411c95349a3c57e538b5
    22 schema:genre chapter
    23 schema:inLanguage en
    24 schema:isAccessibleForFree false
    25 schema:isPartOf Nf8456bd8a5b74f338457094da36c43c2
    26 schema:name Reversible Flowchart Languages and the Structured Reversible Program Theorem
    27 schema:pagination 258-270
    28 schema:productId N42b8d9c6826248f7bb015836b3f40189
    29 N942cba8e0bf343cba9575659bd8cfb65
    30 N96244edeb47744aeb008e460f6947b4f
    31 schema:publisher N3de6f69e34f8425391c6807760f95e8d
    32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022695518
    33 https://doi.org/10.1007/978-3-540-70583-3_22
    34 schema:sdDatePublished 2019-04-15T18:10
    35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    36 schema:sdPublisher N5fffece6626c462588450b80c5aecccb
    37 schema:url http://link.springer.com/10.1007/978-3-540-70583-3_22
    38 sgo:license sg:explorer/license/
    39 sgo:sdDataset chapters
    40 rdf:type schema:Chapter
    41 N0234a7ec3ec345228819cc1459d4e796 rdf:first sg:person.015546427711.73
    42 rdf:rest Nb85fa9dcfde44ef3ad50ae0b4096c5ea
    43 N0f252e2e6fca40359f0c30ba5296fd74 schema:familyName Goldberg
    44 schema:givenName Leslie Ann
    45 rdf:type schema:Person
    46 N151e9a54bca5411c95349a3c57e538b5 rdf:first Nc07e84b4f1504351894618a50ffb87e9
    47 rdf:rest N9d39f4f64c0f40c7800bc44c2c64129e
    48 N19d2123f8edc4ec8b6c4ff96143d69cf rdf:first sg:person.015342016423.59
    49 rdf:rest N0234a7ec3ec345228819cc1459d4e796
    50 N31ac81e75fa349679f078e92ca1e53df rdf:first Nd4cde4a8b6d64475814893da39f013fd
    51 rdf:rest rdf:nil
    52 N3de6f69e34f8425391c6807760f95e8d schema:location Berlin, Heidelberg
    53 schema:name Springer Berlin Heidelberg
    54 rdf:type schema:Organisation
    55 N419c48f32126433aa71eef80dd472a5e rdf:first Na0365874df7a4d0da9bffee5ea013ab1
    56 rdf:rest N7287ea1b35fc41f49b3411e6f77b6509
    57 N42b8d9c6826248f7bb015836b3f40189 schema:name doi
    58 schema:value 10.1007/978-3-540-70583-3_22
    59 rdf:type schema:PropertyValue
    60 N5fffece6626c462588450b80c5aecccb schema:name Springer Nature - SN SciGraph project
    61 rdf:type schema:Organization
    62 N7287ea1b35fc41f49b3411e6f77b6509 rdf:first N9f7df55e8ad3463a988788713af22136
    63 rdf:rest N31ac81e75fa349679f078e92ca1e53df
    64 N942cba8e0bf343cba9575659bd8cfb65 schema:name readcube_id
    65 schema:value 6c1fb7a768d4a6835c86170dd3aacbc159ec6eeb2de665cf8c567713b83d4542
    66 rdf:type schema:PropertyValue
    67 N96244edeb47744aeb008e460f6947b4f schema:name dimensions_id
    68 schema:value pub.1022695518
    69 rdf:type schema:PropertyValue
    70 N9d39f4f64c0f40c7800bc44c2c64129e rdf:first Nfa3a587780824ff5b71e431033575ac1
    71 rdf:rest Ne3dbb2900d714362974c8ca373f71897
    72 N9f7df55e8ad3463a988788713af22136 schema:familyName Ingólfsdóttir
    73 schema:givenName Anna
    74 rdf:type schema:Person
    75 Na0365874df7a4d0da9bffee5ea013ab1 schema:familyName Halldórsson
    76 schema:givenName Magnús M.
    77 rdf:type schema:Person
    78 Nb85fa9dcfde44ef3ad50ae0b4096c5ea rdf:first sg:person.010754010217.31
    79 rdf:rest rdf:nil
    80 Nc07e84b4f1504351894618a50ffb87e9 schema:familyName Aceto
    81 schema:givenName Luca
    82 rdf:type schema:Person
    83 Nd4cde4a8b6d64475814893da39f013fd schema:familyName Walukiewicz
    84 schema:givenName Igor
    85 rdf:type schema:Person
    86 Ne3dbb2900d714362974c8ca373f71897 rdf:first N0f252e2e6fca40359f0c30ba5296fd74
    87 rdf:rest N419c48f32126433aa71eef80dd472a5e
    88 Nf8456bd8a5b74f338457094da36c43c2 schema:isbn 978-3-540-70582-6
    89 978-3-540-70583-3
    90 schema:name Automata, Languages and Programming
    91 rdf:type schema:Book
    92 Nfa3a587780824ff5b71e431033575ac1 schema:familyName Damgård
    93 schema:givenName Ivan
    94 rdf:type schema:Person
    95 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
    96 schema:name Language, Communication and Culture
    97 rdf:type schema:DefinedTerm
    98 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
    99 schema:name Linguistics
    100 rdf:type schema:DefinedTerm
    101 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
    102 schema:familyName Glück
    103 schema:givenName Robert
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    105 rdf:type schema:Person
    106 sg:person.015342016423.59 schema:affiliation https://www.grid.ac/institutes/grid.27476.30
    107 schema:familyName Yokoyama
    108 schema:givenName Tetsuo
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015342016423.59
    110 rdf:type schema:Person
    111 sg:person.015546427711.73 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
    112 schema:familyName Axelsen
    113 schema:givenName Holger Bock
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015546427711.73
    115 rdf:type schema:Person
    116 sg:pub.10.1007/3-540-47018-2_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013466468
    117 https://doi.org/10.1007/3-540-47018-2_2
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/978-1-4612-5983-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045860299
    120 https://doi.org/10.1007/978-1-4612-5983-1
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/978-3-540-74510-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015349256
    123 https://doi.org/10.1007/978-3-540-74510-5_9
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/978-3-540-74593-8_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002680503
    126 https://doi.org/10.1007/978-3-540-74593-8_8
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1016/s0022-0000(77)80007-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1046362897
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1137/0218053 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842152
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.1137/0403020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844611
    133 rdf:type schema:CreativeWork
    134 https://doi.org/10.1145/1062261.1062270 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003907110
    135 rdf:type schema:CreativeWork
    136 https://doi.org/10.1145/1244381.1244404 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006492707
    137 rdf:type schema:CreativeWork
    138 https://doi.org/10.1145/1284621.1284643 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021371811
    139 rdf:type schema:CreativeWork
    140 https://doi.org/10.1145/1366230.1366239 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018780610
    141 rdf:type schema:CreativeWork
    142 https://doi.org/10.1145/355592.365646 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053696262
    143 rdf:type schema:CreativeWork
    144 https://doi.org/10.1145/363534.363539 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014922077
    145 rdf:type schema:CreativeWork
    146 https://doi.org/10.1147/rd.176.0525 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063180324
    147 rdf:type schema:CreativeWork
    148 https://www.grid.ac/institutes/grid.27476.30 schema:alternateName Nagoya University
    149 schema:name NCES, Graduate School of Information Science, Nagoya University,
    150 rdf:type schema:Organization
    151 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
    152 schema:name DIKU, Department of Computer Science, University of Copenhagen,
    153 rdf:type schema:Organization
     




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


    ...