Occam's razor in metacomputation: the notion of a perfect process tree View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1993

AUTHORS

Robert Glück , Andrei V. Klimov

ABSTRACT

We introduce the notion of a perfect process tree as a model for the full propagation of information in metacomputation. Starting with constant propagation we construct step-by-step the driving mechanism used in supercompilation which ensures the perfect propagation of information. The concept of a simple supercompiler based on perfect driving coupled with a simple folding strategy is explained. As an example we demonstrate that specializing a naive pattern matcher with respect to a fixed pattern obtains the efficiency of a matcher generated by the Knuth, Morris & Pratt algorithm. More... »

PAGES

112-123

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-57264-3_34

DOI

http://dx.doi.org/10.1007/3-540-57264-3_34

DIMENSIONS

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


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/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0607", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Plant Biology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Computersprachen, University of Technology Vienna, A-1040, Vienna, Austria", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Institut f\u00fcr Computersprachen, University of Technology Vienna, A-1040, Vienna, Austria"
          ], 
          "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": "Keldysh Institute of Applied Mathematics, Russian Academy of Sciences, 125047, Moscow, Russia", 
          "id": "http://www.grid.ac/institutes/grid.435669.b", 
          "name": [
            "Keldysh Institute of Applied Mathematics, Russian Academy of Sciences, 125047, Moscow, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Klimov", 
        "givenName": "Andrei V.", 
        "id": "sg:person.015026406676.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015026406676.39"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1993", 
    "datePublishedReg": "1993-01-01", 
    "description": "We introduce the notion of a perfect process tree as a model for the full propagation of information in metacomputation. Starting with constant propagation we construct step-by-step the driving mechanism used in supercompilation which ensures the perfect propagation of information. The concept of a simple supercompiler based on perfect driving coupled with a simple folding strategy is explained. As an example we demonstrate that specializing a naive pattern matcher with respect to a fixed pattern obtains the efficiency of a matcher generated by the Knuth, Morris & Pratt algorithm.", 
    "editor": [
      {
        "familyName": "Cousot", 
        "givenName": "Patrick", 
        "type": "Person"
      }, 
      {
        "familyName": "Falaschi", 
        "givenName": "Moreno", 
        "type": "Person"
      }, 
      {
        "familyName": "Fil\u00e9", 
        "givenName": "Gilberto", 
        "type": "Person"
      }, 
      {
        "familyName": "Rauzy", 
        "givenName": "Antoine", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-57264-3_34", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-57264-0", 
        "978-3-540-48027-3"
      ], 
      "name": "Static Analysis", 
      "type": "Book"
    }, 
    "keywords": [
      "trees", 
      "mechanism", 
      "patterns", 
      "step", 
      "information", 
      "strategies", 
      "propagation", 
      "Occam's razor", 
      "razor", 
      "driving mechanism", 
      "example", 
      "efficiency", 
      "notion", 
      "model", 
      "respect", 
      "Morris", 
      "concept", 
      "Knuth", 
      "pattern matcher", 
      "process tree", 
      "constant propagation", 
      "algorithm", 
      "matcher", 
      "perfect process tree", 
      "metacomputation", 
      "supercompilation", 
      "supercompiler", 
      "driving", 
      "Pratt algorithm", 
      "full propagation", 
      "perfect propagation", 
      "simple supercompiler", 
      "perfect driving", 
      "simple folding strategy", 
      "folding strategy", 
      "naive pattern matcher"
    ], 
    "name": "Occam's razor in metacomputation: the notion of a perfect process tree", 
    "pagination": "112-123", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1003987904"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-57264-3_34"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-57264-3_34", 
      "https://app.dimensions.ai/details/publication/pub.1003987904"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:56", 
    "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_339.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-57264-3_34"
  }
]
 

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/3-540-57264-3_34'

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/3-540-57264-3_34'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-57264-3_34'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-57264-3_34'


 

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

121 TRIPLES      23 PREDICATES      62 URIs      55 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-57264-3_34 schema:about anzsrc-for:06
2 anzsrc-for:0607
3 schema:author N23bc48967ab747789adb1d1c83f6b6d6
4 schema:datePublished 1993
5 schema:datePublishedReg 1993-01-01
6 schema:description We introduce the notion of a perfect process tree as a model for the full propagation of information in metacomputation. Starting with constant propagation we construct step-by-step the driving mechanism used in supercompilation which ensures the perfect propagation of information. The concept of a simple supercompiler based on perfect driving coupled with a simple folding strategy is explained. As an example we demonstrate that specializing a naive pattern matcher with respect to a fixed pattern obtains the efficiency of a matcher generated by the Knuth, Morris & Pratt algorithm.
7 schema:editor N1729646dc7c44351902db53b3a7a3ac2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nf6af2332ffb8478f9150aac4a235d0a5
12 schema:keywords Knuth
13 Morris
14 Occam's razor
15 Pratt algorithm
16 algorithm
17 concept
18 constant propagation
19 driving
20 driving mechanism
21 efficiency
22 example
23 folding strategy
24 full propagation
25 information
26 matcher
27 mechanism
28 metacomputation
29 model
30 naive pattern matcher
31 notion
32 pattern matcher
33 patterns
34 perfect driving
35 perfect process tree
36 perfect propagation
37 process tree
38 propagation
39 razor
40 respect
41 simple folding strategy
42 simple supercompiler
43 step
44 strategies
45 supercompilation
46 supercompiler
47 trees
48 schema:name Occam's razor in metacomputation: the notion of a perfect process tree
49 schema:pagination 112-123
50 schema:productId Ne2d76129e9f84eb8b87ba86ec8769ad9
51 Ne8cf3c60a954426fa6250fdbd928dec7
52 schema:publisher Nfe433bedcd0b4eaeb88e1bba42816926
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003987904
54 https://doi.org/10.1007/3-540-57264-3_34
55 schema:sdDatePublished 2021-11-01T18:56
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Nd4c909cf4331459695baf1f364282f5d
58 schema:url https://doi.org/10.1007/3-540-57264-3_34
59 sgo:license sg:explorer/license/
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N047d5c0c7da440468537add72a68d198 rdf:first Naebb4e6b20a84e92ac1d0e3c149493bb
63 rdf:rest Nfcca84689e164e2d9ae74c0ab34ad5b4
64 N1620f0cc3f6b478ab34da5b1cdb0fde7 rdf:first N1dbc52483c854984a351e839820d9a20
65 rdf:rest N047d5c0c7da440468537add72a68d198
66 N1729646dc7c44351902db53b3a7a3ac2 rdf:first N98ce0948a8fd4a2c86579b9658bc2d26
67 rdf:rest N1620f0cc3f6b478ab34da5b1cdb0fde7
68 N1dbc52483c854984a351e839820d9a20 schema:familyName Falaschi
69 schema:givenName Moreno
70 rdf:type schema:Person
71 N23bc48967ab747789adb1d1c83f6b6d6 rdf:first sg:person.010754010217.31
72 rdf:rest N6da44eff55ad4d62ab8ddd0fe570afa2
73 N6da44eff55ad4d62ab8ddd0fe570afa2 rdf:first sg:person.015026406676.39
74 rdf:rest rdf:nil
75 N98ce0948a8fd4a2c86579b9658bc2d26 schema:familyName Cousot
76 schema:givenName Patrick
77 rdf:type schema:Person
78 Naebb4e6b20a84e92ac1d0e3c149493bb schema:familyName Filé
79 schema:givenName Gilberto
80 rdf:type schema:Person
81 Nd4c909cf4331459695baf1f364282f5d schema:name Springer Nature - SN SciGraph project
82 rdf:type schema:Organization
83 Ne2d76129e9f84eb8b87ba86ec8769ad9 schema:name dimensions_id
84 schema:value pub.1003987904
85 rdf:type schema:PropertyValue
86 Ne8cf3c60a954426fa6250fdbd928dec7 schema:name doi
87 schema:value 10.1007/3-540-57264-3_34
88 rdf:type schema:PropertyValue
89 Nf0a0306ccc814be0aa68882c0c20d3de schema:familyName Rauzy
90 schema:givenName Antoine
91 rdf:type schema:Person
92 Nf6af2332ffb8478f9150aac4a235d0a5 schema:isbn 978-3-540-48027-3
93 978-3-540-57264-0
94 schema:name Static Analysis
95 rdf:type schema:Book
96 Nfcca84689e164e2d9ae74c0ab34ad5b4 rdf:first Nf0a0306ccc814be0aa68882c0c20d3de
97 rdf:rest rdf:nil
98 Nfe433bedcd0b4eaeb88e1bba42816926 schema:name Springer Nature
99 rdf:type schema:Organisation
100 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
101 schema:name Biological Sciences
102 rdf:type schema:DefinedTerm
103 anzsrc-for:0607 schema:inDefinedTermSet anzsrc-for:
104 schema:name Plant Biology
105 rdf:type schema:DefinedTerm
106 sg:person.010754010217.31 schema:affiliation grid-institutes:None
107 schema:familyName Glück
108 schema:givenName Robert
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
110 rdf:type schema:Person
111 sg:person.015026406676.39 schema:affiliation grid-institutes:grid.435669.b
112 schema:familyName Klimov
113 schema:givenName Andrei V.
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015026406676.39
115 rdf:type schema:Person
116 grid-institutes:None schema:alternateName Institut für Computersprachen, University of Technology Vienna, A-1040, Vienna, Austria
117 schema:name Institut für Computersprachen, University of Technology Vienna, A-1040, Vienna, Austria
118 rdf:type schema:Organization
119 grid-institutes:grid.435669.b schema:alternateName Keldysh Institute of Applied Mathematics, Russian Academy of Sciences, 125047, Moscow, Russia
120 schema:name Keldysh Institute of Applied Mathematics, Russian Academy of Sciences, 125047, Moscow, Russia
121 rdf:type schema:Organization
 




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


...