Derivation of Deterministic Inverse Programs Based on LR Parsing View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Robert Glück , Masahiko Kawabe

ABSTRACT

We present a method for automatic program inversion of functional programs based on methods of LR parsing. We formalize the transformation and illustrate it with the inversion of a program for run-length encoding. We solve one of the main problems of automatic program inversion—the elimination of nondeterminism—by viewing an inverse program as a context-free grammar and applying to it methods of LR parsing to turn it into a recursive, deterministic inverse program. This improves the efficiency of the inverse programs and greatly expands the application range of our earlier method for program inversion. More... »

PAGES

291-306

References to SciGraph publications

  • 1989. InvX: An automatic function inverter in REWRITING TECHNIQUES AND APPLICATIONS
  • 1996. Program transformation with metasystem transitions: Experiments with a supercompiler in PERSPECTIVES OF SYSTEM INFORMATICS
  • 1981. The Science of Programming in NONE
  • 1979. Program inversion in PROGRAM CONSTRUCTION
  • 2002. Inverting Functions as Folds in MATHEMATICS OF PROGRAM CONSTRUCTION
  • 2002. Principles of Inverse Computation and the Universal Resolving Algorithm in THE ESSENCE OF COMPUTATION
  • 2003. A Program Inverter for a Functional Language with Equality and Constructors in PROGRAMMING LANGUAGES AND SYSTEMS
  • Book

    TITLE

    Functional and Logic Programming

    ISBN

    978-3-540-21402-1
    978-3-540-24754-8

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-24754-8_21

    DOI

    http://dx.doi.org/10.1007/978-3-540-24754-8_21

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "name": [
                "DIKU, PRESTO, JST & University of Copenhagen, DK-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": "Waseda University", 
              "id": "https://www.grid.ac/institutes/grid.5290.e", 
              "name": [
                "Graduate School of Science and Engineering, Waseda University, 169-8555, Tokyo, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kawabe", 
            "givenName": "Masahiko", 
            "id": "sg:person.07742561737.94", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07742561737.94"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-62064-8_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007045901", 
              "https://doi.org/10.1007/3-540-62064-8_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-40018-9_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012065324", 
              "https://doi.org/10.1007/978-3-540-40018-9_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-40018-9_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012065324", 
              "https://doi.org/10.1007/978-3-540-40018-9_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0167-6423(02)00023-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015470010"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0956796800000757", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016061186"
            ], 
            "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"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(81)90014-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019380670"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(81)90014-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019380670"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/115865.115868", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024461452"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45442-x_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030504036", 
              "https://doi.org/10.1007/3-540-45442-x_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/777388.777391", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041853059"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/96877.96953", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043736510"
            ], 
            "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": "sg:pub.10.1007/3-540-36377-7_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051401164", 
              "https://doi.org/10.1007/3-540-36377-7_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-51081-8_139", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053186517", 
              "https://doi.org/10.1007/3-540-51081-8_139"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004", 
        "datePublishedReg": "2004-01-01", 
        "description": "We present a method for automatic program inversion of functional programs based on methods of LR parsing. We formalize the transformation and illustrate it with the inversion of a program for run-length encoding. We solve one of the main problems of automatic program inversion\u2014the elimination of nondeterminism\u2014by viewing an inverse program as a context-free grammar and applying to it methods of LR parsing to turn it into a recursive, deterministic inverse program. This improves the efficiency of the inverse programs and greatly expands the application range of our earlier method for program inversion.", 
        "editor": [
          {
            "familyName": "Kameyama", 
            "givenName": "Yukiyoshi", 
            "type": "Person"
          }, 
          {
            "familyName": "Stuckey", 
            "givenName": "Peter J.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-24754-8_21", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-21402-1", 
            "978-3-540-24754-8"
          ], 
          "name": "Functional and Logic Programming", 
          "type": "Book"
        }, 
        "name": "Derivation of Deterministic Inverse Programs Based on LR Parsing", 
        "pagination": "291-306", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1015138027"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-24754-8_21"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "481f9ddc106ca21c0c6b89b5dde8965034b72a689b3d525cdddcca43a89142f6"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-24754-8_21", 
          "https://app.dimensions.ai/details/publication/pub.1015138027"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:08", 
        "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/0000000360_0000000360/records_118321_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-24754-8_21"
      }
    ]
     

    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-24754-8_21'

    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-24754-8_21'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24754-8_21'

    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-24754-8_21'


     

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

    125 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-24754-8_21 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N6d7acd613ed642dfb4d0fdaa829ce393
    4 schema:citation sg:pub.10.1007/3-540-36377-7_13
    5 sg:pub.10.1007/3-540-45442-x_13
    6 sg:pub.10.1007/3-540-51081-8_139
    7 sg:pub.10.1007/3-540-62064-8_21
    8 sg:pub.10.1007/978-1-4612-5983-1
    9 sg:pub.10.1007/978-3-540-40018-9_17
    10 sg:pub.10.1007/bfb0014657
    11 https://doi.org/10.1016/0004-3702(81)90014-x
    12 https://doi.org/10.1016/s0167-6423(02)00023-0
    13 https://doi.org/10.1017/s0956796800000757
    14 https://doi.org/10.1145/115865.115868
    15 https://doi.org/10.1145/777388.777391
    16 https://doi.org/10.1145/96877.96953
    17 schema:datePublished 2004
    18 schema:datePublishedReg 2004-01-01
    19 schema:description We present a method for automatic program inversion of functional programs based on methods of LR parsing. We formalize the transformation and illustrate it with the inversion of a program for run-length encoding. We solve one of the main problems of automatic program inversion—the elimination of nondeterminism—by viewing an inverse program as a context-free grammar and applying to it methods of LR parsing to turn it into a recursive, deterministic inverse program. This improves the efficiency of the inverse programs and greatly expands the application range of our earlier method for program inversion.
    20 schema:editor Nd684157a2e034e1eb384556bb03e9da9
    21 schema:genre chapter
    22 schema:inLanguage en
    23 schema:isAccessibleForFree false
    24 schema:isPartOf N9220a0f4dc1c44efa2ba9171f75fe2f6
    25 schema:name Derivation of Deterministic Inverse Programs Based on LR Parsing
    26 schema:pagination 291-306
    27 schema:productId N122517e0118a460791ce9224c9552935
    28 N52dc0b62223b4275a6ca7bdbfab8aa19
    29 N70eb0253753d4b978fd2c9d9170b04e1
    30 schema:publisher Ndf9ef879fff34ac49267646b64712133
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015138027
    32 https://doi.org/10.1007/978-3-540-24754-8_21
    33 schema:sdDatePublished 2019-04-16T08:08
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher Nc0ec31758efd439a9675c8fb12e6a61a
    36 schema:url https://link.springer.com/10.1007%2F978-3-540-24754-8_21
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset chapters
    39 rdf:type schema:Chapter
    40 N0de8ee9823004bf9819c38bde1dc4002 rdf:first Nf956061fada7455a997d716207791799
    41 rdf:rest rdf:nil
    42 N122517e0118a460791ce9224c9552935 schema:name readcube_id
    43 schema:value 481f9ddc106ca21c0c6b89b5dde8965034b72a689b3d525cdddcca43a89142f6
    44 rdf:type schema:PropertyValue
    45 N1d87ade11a474bdb933d76b7ad16087e schema:name DIKU, PRESTO, JST & University of Copenhagen, DK-2100, Copenhagen, Denmark
    46 rdf:type schema:Organization
    47 N21db7c39992e46b8bd10aed93c7d743e rdf:first sg:person.07742561737.94
    48 rdf:rest rdf:nil
    49 N52dc0b62223b4275a6ca7bdbfab8aa19 schema:name doi
    50 schema:value 10.1007/978-3-540-24754-8_21
    51 rdf:type schema:PropertyValue
    52 N6d7acd613ed642dfb4d0fdaa829ce393 rdf:first sg:person.010754010217.31
    53 rdf:rest N21db7c39992e46b8bd10aed93c7d743e
    54 N70eb0253753d4b978fd2c9d9170b04e1 schema:name dimensions_id
    55 schema:value pub.1015138027
    56 rdf:type schema:PropertyValue
    57 N9220a0f4dc1c44efa2ba9171f75fe2f6 schema:isbn 978-3-540-21402-1
    58 978-3-540-24754-8
    59 schema:name Functional and Logic Programming
    60 rdf:type schema:Book
    61 Nae21a2b4ed264035bb584587a69a8959 schema:familyName Kameyama
    62 schema:givenName Yukiyoshi
    63 rdf:type schema:Person
    64 Nc0ec31758efd439a9675c8fb12e6a61a schema:name Springer Nature - SN SciGraph project
    65 rdf:type schema:Organization
    66 Nd684157a2e034e1eb384556bb03e9da9 rdf:first Nae21a2b4ed264035bb584587a69a8959
    67 rdf:rest N0de8ee9823004bf9819c38bde1dc4002
    68 Ndf9ef879fff34ac49267646b64712133 schema:location Berlin, Heidelberg
    69 schema:name Springer Berlin Heidelberg
    70 rdf:type schema:Organisation
    71 Nf956061fada7455a997d716207791799 schema:familyName Stuckey
    72 schema:givenName Peter J.
    73 rdf:type schema:Person
    74 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Information and Computing Sciences
    76 rdf:type schema:DefinedTerm
    77 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Artificial Intelligence and Image Processing
    79 rdf:type schema:DefinedTerm
    80 sg:person.010754010217.31 schema:affiliation N1d87ade11a474bdb933d76b7ad16087e
    81 schema:familyName Glück
    82 schema:givenName Robert
    83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    84 rdf:type schema:Person
    85 sg:person.07742561737.94 schema:affiliation https://www.grid.ac/institutes/grid.5290.e
    86 schema:familyName Kawabe
    87 schema:givenName Masahiko
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07742561737.94
    89 rdf:type schema:Person
    90 sg:pub.10.1007/3-540-36377-7_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051401164
    91 https://doi.org/10.1007/3-540-36377-7_13
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/3-540-45442-x_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030504036
    94 https://doi.org/10.1007/3-540-45442-x_13
    95 rdf:type schema:CreativeWork
    96 sg:pub.10.1007/3-540-51081-8_139 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053186517
    97 https://doi.org/10.1007/3-540-51081-8_139
    98 rdf:type schema:CreativeWork
    99 sg:pub.10.1007/3-540-62064-8_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007045901
    100 https://doi.org/10.1007/3-540-62064-8_21
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/978-1-4612-5983-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045860299
    103 https://doi.org/10.1007/978-1-4612-5983-1
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/978-3-540-40018-9_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012065324
    106 https://doi.org/10.1007/978-3-540-40018-9_17
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/bfb0014657 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017699924
    109 https://doi.org/10.1007/bfb0014657
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1016/0004-3702(81)90014-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1019380670
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1016/s0167-6423(02)00023-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015470010
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1017/s0956796800000757 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016061186
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1145/115865.115868 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024461452
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1145/777388.777391 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041853059
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1145/96877.96953 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043736510
    122 rdf:type schema:CreativeWork
    123 https://www.grid.ac/institutes/grid.5290.e schema:alternateName Waseda University
    124 schema:name Graduate School of Science and Engineering, Waseda University, 169-8555, Tokyo, Japan
    125 rdf:type schema:Organization
     




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


    ...