Inverse computation and the Universal Resolving Algorithm View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2001-03

AUTHORS

Sergei Abramov, Robert Glück

ABSTRACT

We survey fundamental concepts for inverse programming and then present the Universal Resolving Algorithm, an algorithm for inverse computation in a first-order, functional programming language. We discuss the key concepts of the algorithm, including a three-step approach based on the notion of a perfect process tree, and demonstrate our implementation with several examples of inverse computation. More... »

PAGES

31-45

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
  • 1993. Occam's razor in metacomputation: the notion of a perfect process tree in STATIC ANALYSIS
  • 1994. The essence of program transformation by partial evaluation and driving in LOGIC, LANGUAGE AND COMPUTATION
  • 1994. Partial deduction and driving are equivalent in PROGRAMMING LANGUAGE IMPLEMENTATION AND LOGIC PROGRAMMING
  • 1999. An Introduction to Online and Offline Partial Evaluation Using a Simple Flowchart Language in PARTIAL EVALUATION
  • 2000. The Universal Resolving Algorithm: Inverse Computation in a Functional Language in MATHEMATICS OF PROGRAM CONSTRUCTION
  • 1987. Foundations of Logic Programming in NONE
  • 1997-05. Running programs backwards: The logical inversion of imperative computation in FORMAL ASPECTS OF COMPUTING
  • 1992-03. On the synthesis of function inverses in ACTA INFORMATICA
  • 2000-11-24. Combining Semantics with Non-standard Interpreter Hierarchies in FST TCS 2000: FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • 2000-01-28. On Perfect Supercompilation in PERSPECTIVES OF SYSTEM INFORMATICS
  • 1996. A roadmap to metacomputation by supercompilation in PARTIAL EVALUATION
  • 1998-03. On the degeneration of program generators by program composition in NEW GENERATION COMPUTING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf03160224

    DOI

    http://dx.doi.org/10.1007/bf03160224

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Program Systems Institute Russian Academy of Sciences, RU-152140, Pereslavl-Zalessky, Russia", 
              "id": "http://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": "PRESTO, JST & Institute for Software Production Technology, Waseda University, 169-8555, Tokyo, Japan", 
              "id": "http://www.grid.ac/institutes/grid.5290.e", 
              "name": [
                "PRESTO, JST & Institute for Software Production Technology, Waseda University, 169-8555, Tokyo, Japan"
              ], 
              "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/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": "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": "sg:pub.10.1007/978-3-642-83189-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016029570", 
              "https://doi.org/10.1007/978-3-642-83189-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-61580-6_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008923491", 
              "https://doi.org/10.1007/3-540-61580-6_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0032402", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027875008", 
              "https://doi.org/10.1007/bfb0032402"
            ], 
            "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": "sg:pub.10.1007/bf01211087", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008568428", 
              "https://doi.org/10.1007/bf01211087"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01185679", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024052891", 
              "https://doi.org/10.1007/bf01185679"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44450-5_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040007835", 
              "https://doi.org/10.1007/3-540-44450-5_16"
            ], 
            "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-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/bf03037321", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042200080", 
              "https://doi.org/10.1007/bf03037321"
            ], 
            "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/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"
          }, 
          {
            "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"
          }
        ], 
        "datePublished": "2001-03", 
        "datePublishedReg": "2001-03-01", 
        "description": "We survey fundamental concepts for inverse programming and then present the Universal Resolving Algorithm, an algorithm for inverse computation in a first-order, functional programming language. We discuss the key concepts of the algorithm, including a three-step approach based on the notion of a perfect process tree, and demonstrate our implementation with several examples of inverse computation.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf03160224", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1135877", 
            "issn": [
              "1007-1202", 
              "1993-4998"
            ], 
            "name": "Wuhan University Journal of Natural Sciences", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1-2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "6"
          }
        ], 
        "keywords": [
          "inverse computation", 
          "functional programming language", 
          "programming language", 
          "Universal Resolving Algorithm", 
          "algorithm", 
          "process tree", 
          "three-step approach", 
          "perfect process tree", 
          "computation", 
          "inverse programming", 
          "fundamental concepts", 
          "key concepts", 
          "programming", 
          "implementation", 
          "language", 
          "concept", 
          "trees", 
          "example", 
          "notion", 
          "approach", 
          "Resolving Algorithm"
        ], 
        "name": "Inverse computation and the Universal Resolving Algorithm", 
        "pagination": "31-45", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1019905096"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf03160224"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf03160224", 
          "https://app.dimensions.ai/details/publication/pub.1019905096"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-11-01T18:04", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/article/article_332.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf03160224"
      }
    ]
     

    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/bf03160224'

    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/bf03160224'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf03160224'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf03160224'


     

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

    149 TRIPLES      22 PREDICATES      62 URIs      39 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf03160224 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N25cc290ffd264f958f699f41cc21b764
    4 schema:citation sg:pub.10.1007/10722010_13
    5 sg:pub.10.1007/3-540-44450-5_16
    6 sg:pub.10.1007/3-540-46562-6_10
    7 sg:pub.10.1007/3-540-47018-2_2
    8 sg:pub.10.1007/3-540-51081-8_139
    9 sg:pub.10.1007/3-540-57264-3_34
    10 sg:pub.10.1007/3-540-58402-1_13
    11 sg:pub.10.1007/3-540-61580-6_8
    12 sg:pub.10.1007/3-540-62064-8_21
    13 sg:pub.10.1007/978-1-4612-5983-1
    14 sg:pub.10.1007/978-3-642-83189-8
    15 sg:pub.10.1007/bf01185679
    16 sg:pub.10.1007/bf01211087
    17 sg:pub.10.1007/bf03037321
    18 sg:pub.10.1007/bfb0032402
    19 schema:datePublished 2001-03
    20 schema:datePublishedReg 2001-03-01
    21 schema:description We survey fundamental concepts for inverse programming and then present the Universal Resolving Algorithm, an algorithm for inverse computation in a first-order, functional programming language. We discuss the key concepts of the algorithm, including a three-step approach based on the notion of a perfect process tree, and demonstrate our implementation with several examples of inverse computation.
    22 schema:genre article
    23 schema:inLanguage en
    24 schema:isAccessibleForFree false
    25 schema:isPartOf N543ff7bfc2cd4f1cb3ee6a868ea359a7
    26 Nac4b25161bca46df8bb17ab415845c57
    27 sg:journal.1135877
    28 schema:keywords Resolving Algorithm
    29 Universal Resolving Algorithm
    30 algorithm
    31 approach
    32 computation
    33 concept
    34 example
    35 functional programming language
    36 fundamental concepts
    37 implementation
    38 inverse computation
    39 inverse programming
    40 key concepts
    41 language
    42 notion
    43 perfect process tree
    44 process tree
    45 programming
    46 programming language
    47 three-step approach
    48 trees
    49 schema:name Inverse computation and the Universal Resolving Algorithm
    50 schema:pagination 31-45
    51 schema:productId N441bb884bdf244b9b4eea7c3dbce1fa6
    52 Nad4a1b8e4c994833ac1485a2ff3f031a
    53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019905096
    54 https://doi.org/10.1007/bf03160224
    55 schema:sdDatePublished 2021-11-01T18:04
    56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    57 schema:sdPublisher N089ac4ec71b54df28ce592e1fdcda8ae
    58 schema:url https://doi.org/10.1007/bf03160224
    59 sgo:license sg:explorer/license/
    60 sgo:sdDataset articles
    61 rdf:type schema:ScholarlyArticle
    62 N089ac4ec71b54df28ce592e1fdcda8ae schema:name Springer Nature - SN SciGraph project
    63 rdf:type schema:Organization
    64 N25cc290ffd264f958f699f41cc21b764 rdf:first sg:person.010307436465.27
    65 rdf:rest N4778d3bf249a4a9c97881a251308a0b3
    66 N441bb884bdf244b9b4eea7c3dbce1fa6 schema:name dimensions_id
    67 schema:value pub.1019905096
    68 rdf:type schema:PropertyValue
    69 N4778d3bf249a4a9c97881a251308a0b3 rdf:first sg:person.010754010217.31
    70 rdf:rest rdf:nil
    71 N543ff7bfc2cd4f1cb3ee6a868ea359a7 schema:volumeNumber 6
    72 rdf:type schema:PublicationVolume
    73 Nac4b25161bca46df8bb17ab415845c57 schema:issueNumber 1-2
    74 rdf:type schema:PublicationIssue
    75 Nad4a1b8e4c994833ac1485a2ff3f031a schema:name doi
    76 schema:value 10.1007/bf03160224
    77 rdf:type schema:PropertyValue
    78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Information and Computing Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Computation Theory and Mathematics
    83 rdf:type schema:DefinedTerm
    84 sg:journal.1135877 schema:issn 1007-1202
    85 1993-4998
    86 schema:name Wuhan University Journal of Natural Sciences
    87 schema:publisher Springer Nature
    88 rdf:type schema:Periodical
    89 sg:person.010307436465.27 schema:affiliation grid-institutes:grid.4886.2
    90 schema:familyName Abramov
    91 schema:givenName Sergei
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010307436465.27
    93 rdf:type schema:Person
    94 sg:person.010754010217.31 schema:affiliation grid-institutes:grid.5290.e
    95 schema:familyName Glück
    96 schema:givenName Robert
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    98 rdf:type schema:Person
    99 sg:pub.10.1007/10722010_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048205783
    100 https://doi.org/10.1007/10722010_13
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/3-540-44450-5_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040007835
    103 https://doi.org/10.1007/3-540-44450-5_16
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/3-540-46562-6_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016922795
    106 https://doi.org/10.1007/3-540-46562-6_10
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/3-540-47018-2_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013466468
    109 https://doi.org/10.1007/3-540-47018-2_2
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/3-540-51081-8_139 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053186517
    112 https://doi.org/10.1007/3-540-51081-8_139
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/3-540-57264-3_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003987904
    115 https://doi.org/10.1007/3-540-57264-3_34
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/3-540-58402-1_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026985651
    118 https://doi.org/10.1007/3-540-58402-1_13
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/3-540-61580-6_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008923491
    121 https://doi.org/10.1007/3-540-61580-6_8
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/3-540-62064-8_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007045901
    124 https://doi.org/10.1007/3-540-62064-8_21
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/978-1-4612-5983-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045860299
    127 https://doi.org/10.1007/978-1-4612-5983-1
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/978-3-642-83189-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016029570
    130 https://doi.org/10.1007/978-3-642-83189-8
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/bf01185679 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024052891
    133 https://doi.org/10.1007/bf01185679
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/bf01211087 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008568428
    136 https://doi.org/10.1007/bf01211087
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/bf03037321 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042200080
    139 https://doi.org/10.1007/bf03037321
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/bfb0032402 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027875008
    142 https://doi.org/10.1007/bfb0032402
    143 rdf:type schema:CreativeWork
    144 grid-institutes:grid.4886.2 schema:alternateName Program Systems Institute Russian Academy of Sciences, RU-152140, Pereslavl-Zalessky, Russia
    145 schema:name Program Systems Institute Russian Academy of Sciences, RU-152140, Pereslavl-Zalessky, Russia
    146 rdf:type schema:Organization
    147 grid-institutes:grid.5290.e schema:alternateName PRESTO, JST & Institute for Software Production Technology, Waseda University, 169-8555, Tokyo, Japan
    148 schema:name PRESTO, JST & Institute for Software Production Technology, Waseda University, 169-8555, Tokyo, Japan
    149 rdf:type schema:Organization
     




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


    ...