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-11-01T18:48", 
    "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/chapter/chapter_17.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 Na789f3e44fed4673b1114878e2990666
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 N12c08c0b092041618344f7da74712d18
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ndffb1e8bdc644b8f949b5747c3bf68b6
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 N87d60d9ffb5746b98631e7a9a1c36811
43 Nf97b20c1b2e8411f80f814fd6424e6be
44 schema:publisher Ne177479bbe34471fa997a9bdb72f6082
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048205783
46 https://doi.org/10.1007/10722010_13
47 schema:sdDatePublished 2021-11-01T18:48
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher Ncc067b0ec42f4daeb80a473bf9d8110a
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 N12c08c0b092041618344f7da74712d18 rdf:first N910b506572a5472fad9f85c501146066
55 rdf:rest N594b3b3b54504b988147f0dc2dc4a737
56 N4b0cdf5117f0426e94397a9296196745 rdf:first sg:person.010754010217.31
57 rdf:rest rdf:nil
58 N594b3b3b54504b988147f0dc2dc4a737 rdf:first Nc50198cfeb8a4ecd8c018c48066891d7
59 rdf:rest rdf:nil
60 N87d60d9ffb5746b98631e7a9a1c36811 schema:name dimensions_id
61 schema:value pub.1048205783
62 rdf:type schema:PropertyValue
63 N910b506572a5472fad9f85c501146066 schema:familyName Backhouse
64 schema:givenName Roland
65 rdf:type schema:Person
66 Na789f3e44fed4673b1114878e2990666 rdf:first sg:person.010307436465.27
67 rdf:rest N4b0cdf5117f0426e94397a9296196745
68 Nc50198cfeb8a4ecd8c018c48066891d7 schema:familyName Oliveira
69 schema:givenName José Nuno
70 rdf:type schema:Person
71 Ncc067b0ec42f4daeb80a473bf9d8110a schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 Ndffb1e8bdc644b8f949b5747c3bf68b6 schema:isbn 978-3-540-45025-2
74 978-3-540-67727-7
75 schema:name Mathematics of Program Construction
76 rdf:type schema:Book
77 Ne177479bbe34471fa997a9bdb72f6082 schema:name Springer Nature
78 rdf:type schema:Organisation
79 Nf97b20c1b2e8411f80f814fd6424e6be schema:name doi
80 schema:value 10.1007/10722010_13
81 rdf:type schema:PropertyValue
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)


...