The Universal Resolving Algorithm: Inverse Computation in a Functional Language View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000

AUTHORS

Sergei Abramov , Robert Glück

ABSTRACT

We present an algorithm for inverse computation in a first-order functional language based on the notion of a perfect process tree. The Universal Resolving Algorithm (URA) introduced in this paper is sound and complete, and computes each solution, if it exists, in finite time. The algorithm has been implemented for TSG, a typed dialect of S-Graph, and shows some remarkable results for the inverse computation of functional programs such as pattern matching and the inverse interpretation of While-programs. More... »

PAGES

187-212

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/10722010_13

DOI

http://dx.doi.org/10.1007/10722010_13

DIMENSIONS

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


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": "Department of Information and Computer Science, School of Science and Engineering, Waseda University, Shinjuku-ku, 169-8555, Tokyo, Japan", 
          "id": "http://www.grid.ac/institutes/grid.5290.e", 
          "name": [
            "Department of Information and Computer Science, School of Science and Engineering, Waseda University, Shinjuku-ku, 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"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "We present an algorithm for inverse computation in a first-order functional language based on the notion of a perfect process tree. The Universal Resolving Algorithm (URA) introduced in this paper is sound and complete, and computes each solution, if it exists, in finite time. The algorithm has been implemented for TSG, a typed dialect of S-Graph, and shows some remarkable results for the inverse computation of functional programs such as pattern matching and the inverse interpretation of While-programs.", 
    "editor": [
      {
        "familyName": "Backhouse", 
        "givenName": "Roland", 
        "type": "Person"
      }, 
      {
        "familyName": "Oliveira", 
        "givenName": "Jos\u00e9 Nuno", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/10722010_13", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67727-7", 
        "978-3-540-45025-2"
      ], 
      "name": "Mathematics of Program Construction", 
      "type": "Book"
    }, 
    "keywords": [
      "TSG", 
      "program", 
      "time", 
      "inverse computation", 
      "functional language", 
      "results", 
      "Universal Resolving Algorithm", 
      "first-order functional language", 
      "pattern matching", 
      "algorithm", 
      "remarkable results", 
      "perfect process tree", 
      "process tree", 
      "functional programs", 
      "computation", 
      "interpretation", 
      "language", 
      "compute", 
      "finite time", 
      "graph", 
      "matching", 
      "notion", 
      "trees", 
      "solution", 
      "inverse interpretation", 
      "dialects", 
      "paper", 
      "Resolving Algorithm"
    ], 
    "name": "The Universal Resolving Algorithm: Inverse Computation in a Functional Language", 
    "pagination": "187-212", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048205783"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/10722010_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/10722010_13", 
      "https://app.dimensions.ai/details/publication/pub.1048205783"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:55", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_108.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/10722010_13"
  }
]
 

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/10722010_13'

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/10722010_13'

Turtle is a human-readable linked data format.

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

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

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


 

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

103 TRIPLES      23 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/10722010_13 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ne166700c07e748dfbc80015a3a08a239
4 schema:datePublished 2000
5 schema:datePublishedReg 2000-01-01
6 schema:description We present an algorithm for inverse computation in a first-order functional language based on the notion of a perfect process tree. The Universal Resolving Algorithm (URA) introduced in this paper is sound and complete, and computes each solution, if it exists, in finite time. The algorithm has been implemented for TSG, a typed dialect of S-Graph, and shows some remarkable results for the inverse computation of functional programs such as pattern matching and the inverse interpretation of While-programs.
7 schema:editor Nabd0a76103cf4d6aa8ae507dfaf23a0a
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nc30c26706e114d0b86cc36e9e5c6a20a
12 schema:keywords Resolving Algorithm
13 TSG
14 Universal Resolving Algorithm
15 algorithm
16 computation
17 compute
18 dialects
19 finite time
20 first-order functional language
21 functional language
22 functional programs
23 graph
24 interpretation
25 inverse computation
26 inverse interpretation
27 language
28 matching
29 notion
30 paper
31 pattern matching
32 perfect process tree
33 process tree
34 program
35 remarkable results
36 results
37 solution
38 time
39 trees
40 schema:name The Universal Resolving Algorithm: Inverse Computation in a Functional Language
41 schema:pagination 187-212
42 schema:productId Nc4a26c23bef04b4d86aa1f563283623e
43 Nc6b3b4e079544db0927e8125599c6759
44 schema:publisher Na004094d36d744df93378799a3ae1d6d
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048205783
46 https://doi.org/10.1007/10722010_13
47 schema:sdDatePublished 2021-12-01T19:55
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher Nc6b27c950c6a423399518c873b9ab104
50 schema:url https://doi.org/10.1007/10722010_13
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N444b8cfcb2fe4aacb5eb1e349aaac08b schema:familyName Oliveira
55 schema:givenName José Nuno
56 rdf:type schema:Person
57 N55651b2e54f644ad9b74124bafc144a7 rdf:first sg:person.010754010217.31
58 rdf:rest rdf:nil
59 N70f33f4ef05b409aa61b575989d74d40 rdf:first N444b8cfcb2fe4aacb5eb1e349aaac08b
60 rdf:rest rdf:nil
61 N7339feceefe8481da04bca4c7c71e2d7 schema:familyName Backhouse
62 schema:givenName Roland
63 rdf:type schema:Person
64 Na004094d36d744df93378799a3ae1d6d schema:name Springer Nature
65 rdf:type schema:Organisation
66 Nabd0a76103cf4d6aa8ae507dfaf23a0a rdf:first N7339feceefe8481da04bca4c7c71e2d7
67 rdf:rest N70f33f4ef05b409aa61b575989d74d40
68 Nc30c26706e114d0b86cc36e9e5c6a20a schema:isbn 978-3-540-45025-2
69 978-3-540-67727-7
70 schema:name Mathematics of Program Construction
71 rdf:type schema:Book
72 Nc4a26c23bef04b4d86aa1f563283623e schema:name doi
73 schema:value 10.1007/10722010_13
74 rdf:type schema:PropertyValue
75 Nc6b27c950c6a423399518c873b9ab104 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 Nc6b3b4e079544db0927e8125599c6759 schema:name dimensions_id
78 schema:value pub.1048205783
79 rdf:type schema:PropertyValue
80 Ne166700c07e748dfbc80015a3a08a239 rdf:first sg:person.010307436465.27
81 rdf:rest N55651b2e54f644ad9b74124bafc144a7
82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
83 schema:name Information and Computing Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
86 schema:name Computation Theory and Mathematics
87 rdf:type schema:DefinedTerm
88 sg:person.010307436465.27 schema:affiliation grid-institutes:grid.4886.2
89 schema:familyName Abramov
90 schema:givenName Sergei
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010307436465.27
92 rdf:type schema:Person
93 sg:person.010754010217.31 schema:affiliation grid-institutes:grid.5290.e
94 schema:familyName Glück
95 schema:givenName Robert
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
97 rdf:type schema:Person
98 grid-institutes:grid.4886.2 schema:alternateName Program Systems Institute, Russian Academy of Sciences, RU-152140, Pereslavl-Zalessky, Russia
99 schema:name Program Systems Institute, Russian Academy of Sciences, RU-152140, Pereslavl-Zalessky, Russia
100 rdf:type schema:Organization
101 grid-institutes:grid.5290.e schema:alternateName Department of Information and Computer Science, School of Science and Engineering, Waseda University, Shinjuku-ku, 169-8555, Tokyo, Japan
102 schema:name Department of Information and Computer Science, School of Science and Engineering, Waseda University, Shinjuku-ku, 169-8555, Tokyo, Japan
103 rdf:type schema:Organization
 




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


...