An Universal Resolving Algorithm for Inverse Computation of Lazy Languages View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007

AUTHORS

Sergei Abramov , Robert Glück , Yuri Klimov

ABSTRACT

The Universal Resolving Algorithm was originally formulated for inverse computation of tail-recursive programs. We present an extension to general recursion that improves the efficiency and termination of inverse computation because partially produced output is used to reduce the search space. In addition, we present a transformation using a new unification-based equality operator. Examples demonstrate the advantages of the new technique. We found that these extensions can also improve inverse computation in the context of functional-logic languages. More... »

PAGES

27-40

References to SciGraph publications

  • 1996. Program transformation with metasystem transitions: Experiments with a supercompiler in PERSPECTIVES OF SYSTEM INFORMATICS
  • 1993. Occam's razor in metacomputation: the notion of a perfect process tree in STATIC ANALYSIS
  • 1994. Partial deduction and driving are equivalent in PROGRAMMING LANGUAGE IMPLEMENTATION AND LOGIC PROGRAMMING
  • 2002. Inverting Functions as Folds in MATHEMATICS OF PROGRAM CONSTRUCTION
  • 2000. The Universal Resolving Algorithm: Inverse Computation in a Functional Language in MATHEMATICS OF PROGRAM CONSTRUCTION
  • 2000-01-28. On Perfect Supercompilation in PERSPECTIVES OF SYSTEM INFORMATICS
  • 2001. Driving in the Jungle in PROGRAMS AS DATA OBJECTS
  • 2002-03. The narrowing-driven approach to functional logic program specialization in NEW GENERATION COMPUTING
  • Book

    TITLE

    Perspectives of Systems Informatics

    ISBN

    978-3-540-70880-3
    978-3-540-70881-0

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-70881-0_6

    DOI

    http://dx.doi.org/10.1007/978-3-540-70881-0_6

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "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": {
              "alternateName": "Russian Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.4886.2", 
              "name": [
                "Program Systems Institute, Russian Academy of Sciences, RU-152140 Pereslavl-Zalessky, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Abramov", 
            "givenName": "Sergei", 
            "id": "sg:person.010307436465.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010307436465.27"
            ], 
            "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, 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": "Russian Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.4886.2", 
              "name": [
                "M.V. Keldysh Institute for Applied Mathematics, Russian Academy of Sciences, RU-125047 Moscow, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Klimov", 
            "givenName": "Yuri", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-44978-7_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001084477", 
              "https://doi.org/10.1007/3-540-44978-7_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf03037257", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002140766", 
              "https://doi.org/10.1007/bf03037257"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/503032.503036", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003136973"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-57264-3_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003987904", 
              "https://doi.org/10.1007/3-540-57264-3_34"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "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": "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.1145/5956.5957", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016193336"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46562-6_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016922795", 
              "https://doi.org/10.1007/3-540-46562-6_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46562-6_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016922795", 
              "https://doi.org/10.1007/3-540-46562-6_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-58402-1_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026985651", 
              "https://doi.org/10.1007/3-540-58402-1_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0743-1066(94)90034-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028239269"
            ], 
            "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": "sg:pub.10.1007/10722010_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048205783", 
              "https://doi.org/10.1007/10722010_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/10722010_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048205783", 
              "https://doi.org/10.1007/10722010_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0743-1066(92)90024-w", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051087157"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1051/ita/1991250504451", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1083550378"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007", 
        "datePublishedReg": "2007-01-01", 
        "description": "The Universal Resolving Algorithm was originally formulated for inverse computation of tail-recursive programs. We present an extension to general recursion that improves the efficiency and termination of inverse computation because partially produced output is used to reduce the search space. In addition, we present a transformation using a new unification-based equality operator. Examples demonstrate the advantages of the new technique. We found that these extensions can also improve inverse computation in the context of functional-logic languages.", 
        "editor": [
          {
            "familyName": "Virbitskaite", 
            "givenName": "Irina", 
            "type": "Person"
          }, 
          {
            "familyName": "Voronkov", 
            "givenName": "Andrei", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-70881-0_6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-70880-3", 
            "978-3-540-70881-0"
          ], 
          "name": "Perspectives of Systems Informatics", 
          "type": "Book"
        }, 
        "name": "An Universal Resolving Algorithm for Inverse Computation of Lazy Languages", 
        "pagination": "27-40", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-70881-0_6"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "e0ef08baadc0f66009c4d8b09a679b35c33286e5384a50db65ebb272e0211fc6"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1047218411"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-70881-0_6", 
          "https://app.dimensions.ai/details/publication/pub.1047218411"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:22", 
        "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/0000000339_0000000339/records_109518_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-70881-0_6"
      }
    ]
     

    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-70881-0_6'

    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-70881-0_6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70881-0_6'

    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-70881-0_6'


     

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

    137 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-70881-0_6 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N31c68fae2139451d9ae6b56a0f08f7f5
    4 schema:citation sg:pub.10.1007/10722010_13
    5 sg:pub.10.1007/3-540-44978-7_12
    6 sg:pub.10.1007/3-540-45442-x_13
    7 sg:pub.10.1007/3-540-46562-6_10
    8 sg:pub.10.1007/3-540-57264-3_34
    9 sg:pub.10.1007/3-540-58402-1_13
    10 sg:pub.10.1007/3-540-62064-8_21
    11 sg:pub.10.1007/bf03037257
    12 https://doi.org/10.1016/0743-1066(92)90024-w
    13 https://doi.org/10.1016/0743-1066(94)90034-5
    14 https://doi.org/10.1016/s0167-6423(02)00023-0
    15 https://doi.org/10.1051/ita/1991250504451
    16 https://doi.org/10.1145/503032.503036
    17 https://doi.org/10.1145/5956.5957
    18 schema:datePublished 2007
    19 schema:datePublishedReg 2007-01-01
    20 schema:description The Universal Resolving Algorithm was originally formulated for inverse computation of tail-recursive programs. We present an extension to general recursion that improves the efficiency and termination of inverse computation because partially produced output is used to reduce the search space. In addition, we present a transformation using a new unification-based equality operator. Examples demonstrate the advantages of the new technique. We found that these extensions can also improve inverse computation in the context of functional-logic languages.
    21 schema:editor N9ecc716741ea4ff7975d9c72160ce642
    22 schema:genre chapter
    23 schema:inLanguage en
    24 schema:isAccessibleForFree false
    25 schema:isPartOf N5db2da0ddf9f46a28ed2603d75f6e3cc
    26 schema:name An Universal Resolving Algorithm for Inverse Computation of Lazy Languages
    27 schema:pagination 27-40
    28 schema:productId N39bf5366b1704844afa121a71b1a8a5d
    29 N84a2411ace774053b897f56e7b10e3ea
    30 Nae3c9b690ea940d7a338302cff3b8710
    31 schema:publisher Ne62e8b92435c40d2b34ea3f99694852b
    32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047218411
    33 https://doi.org/10.1007/978-3-540-70881-0_6
    34 schema:sdDatePublished 2019-04-16T05:22
    35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    36 schema:sdPublisher N9a80ba3dbecd4cef893135b8e6eb2716
    37 schema:url https://link.springer.com/10.1007%2F978-3-540-70881-0_6
    38 sgo:license sg:explorer/license/
    39 sgo:sdDataset chapters
    40 rdf:type schema:Chapter
    41 N31c68fae2139451d9ae6b56a0f08f7f5 rdf:first sg:person.010307436465.27
    42 rdf:rest Nd3e29a8f48ad4622b3680da0659aceb9
    43 N39bf5366b1704844afa121a71b1a8a5d schema:name doi
    44 schema:value 10.1007/978-3-540-70881-0_6
    45 rdf:type schema:PropertyValue
    46 N5db2da0ddf9f46a28ed2603d75f6e3cc schema:isbn 978-3-540-70880-3
    47 978-3-540-70881-0
    48 schema:name Perspectives of Systems Informatics
    49 rdf:type schema:Book
    50 N62e636f58d054ccdaaa448636bff161b rdf:first Nf9b97a70cd7f442a8b89c9a678a4613f
    51 rdf:rest rdf:nil
    52 N6321be8b82da4b6dae55ea792eb429a9 schema:affiliation https://www.grid.ac/institutes/grid.4886.2
    53 schema:familyName Klimov
    54 schema:givenName Yuri
    55 rdf:type schema:Person
    56 N84a2411ace774053b897f56e7b10e3ea schema:name dimensions_id
    57 schema:value pub.1047218411
    58 rdf:type schema:PropertyValue
    59 N9a80ba3dbecd4cef893135b8e6eb2716 schema:name Springer Nature - SN SciGraph project
    60 rdf:type schema:Organization
    61 N9e1cb4ad9a7a497ea37307d273440d8b schema:familyName Virbitskaite
    62 schema:givenName Irina
    63 rdf:type schema:Person
    64 N9ecc716741ea4ff7975d9c72160ce642 rdf:first N9e1cb4ad9a7a497ea37307d273440d8b
    65 rdf:rest N62e636f58d054ccdaaa448636bff161b
    66 Na8046b1e84de4100821b0a2a29f88ff3 rdf:first N6321be8b82da4b6dae55ea792eb429a9
    67 rdf:rest rdf:nil
    68 Nae3c9b690ea940d7a338302cff3b8710 schema:name readcube_id
    69 schema:value e0ef08baadc0f66009c4d8b09a679b35c33286e5384a50db65ebb272e0211fc6
    70 rdf:type schema:PropertyValue
    71 Nd3e29a8f48ad4622b3680da0659aceb9 rdf:first sg:person.010754010217.31
    72 rdf:rest Na8046b1e84de4100821b0a2a29f88ff3
    73 Ne62e8b92435c40d2b34ea3f99694852b schema:location Berlin, Heidelberg
    74 schema:name Springer Berlin Heidelberg
    75 rdf:type schema:Organisation
    76 Nf9b97a70cd7f442a8b89c9a678a4613f schema:familyName Voronkov
    77 schema:givenName Andrei
    78 rdf:type schema:Person
    79 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    80 schema:name Information and Computing Sciences
    81 rdf:type schema:DefinedTerm
    82 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    83 schema:name Computation Theory and Mathematics
    84 rdf:type schema:DefinedTerm
    85 sg:person.010307436465.27 schema:affiliation https://www.grid.ac/institutes/grid.4886.2
    86 schema:familyName Abramov
    87 schema:givenName Sergei
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010307436465.27
    89 rdf:type schema:Person
    90 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
    91 schema:familyName Glück
    92 schema:givenName Robert
    93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    94 rdf:type schema:Person
    95 sg:pub.10.1007/10722010_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048205783
    96 https://doi.org/10.1007/10722010_13
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/3-540-44978-7_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001084477
    99 https://doi.org/10.1007/3-540-44978-7_12
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/3-540-45442-x_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030504036
    102 https://doi.org/10.1007/3-540-45442-x_13
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/3-540-46562-6_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016922795
    105 https://doi.org/10.1007/3-540-46562-6_10
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/3-540-57264-3_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003987904
    108 https://doi.org/10.1007/3-540-57264-3_34
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/3-540-58402-1_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026985651
    111 https://doi.org/10.1007/3-540-58402-1_13
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/3-540-62064-8_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007045901
    114 https://doi.org/10.1007/3-540-62064-8_21
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/bf03037257 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002140766
    117 https://doi.org/10.1007/bf03037257
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1016/0743-1066(92)90024-w schema:sameAs https://app.dimensions.ai/details/publication/pub.1051087157
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1016/0743-1066(94)90034-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028239269
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1016/s0167-6423(02)00023-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015470010
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1051/ita/1991250504451 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083550378
    126 rdf:type schema:CreativeWork
    127 https://doi.org/10.1145/503032.503036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003136973
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.1145/5956.5957 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016193336
    130 rdf:type schema:CreativeWork
    131 https://www.grid.ac/institutes/grid.4886.2 schema:alternateName Russian Academy of Sciences
    132 schema:name M.V. Keldysh Institute for Applied Mathematics, Russian Academy of Sciences, RU-125047 Moscow, Russia
    133 Program Systems Institute, Russian Academy of Sciences, RU-152140 Pereslavl-Zalessky, Russia
    134 rdf:type schema:Organization
    135 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
    136 schema:name DIKU, Department of Computer Science, University of Copenhagen, DK-2100 Copenhagen, Denmark
    137 rdf:type schema:Organization
     




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


    ...