The Universality of Higher-Order Attributed Tree Transducers View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2000-02

AUTHORS

T. Noll, H. Vogler

ABSTRACT

. In this paper we present higher-order attributed tree transducers as a formal computational model for higher-order attribute grammars. The latter is a generalization of the classical concept of attribute grammars in the sense that during attribute evaluation, the input tree can be enlarged by inserting subtrees which were computed during attribute evaluation. We prove the universality of this formalism by showing that the class of functions described by higher-order attributed tree transducers coincides with the class of (partial) recursive tree functions. More... »

PAGES

45-75

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "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"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "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"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0805", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Distributed Computing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Teleinformatics, noll@it.kth.se, Royal Institute of Technology (KTH), Electrum 204, S-16440 Kista, Sweden, SE", 
          "id": "http://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "Department of Teleinformatics, noll@it.kth.se, Royal Institute of Technology (KTH), Electrum 204, S-16440 Kista, Sweden, SE"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Noll", 
        "givenName": "T.", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institut für Softwaretechnik I,vogler@inf.tu-dresden.de, Dresden University of Technology,   D-01062 Dresden, Germany, DE", 
          "id": "http://www.grid.ac/institutes/grid.4488.0", 
          "name": [
            "Institut für Softwaretechnik I,vogler@inf.tu-dresden.de, Dresden University of Technology,   D-01062 Dresden, Germany, DE"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vogler", 
        "givenName": "H.", 
        "id": "sg:person.014562633673.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000-02", 
    "datePublishedReg": "2000-02-01", 
    "description": "Abstract.  In this paper we present higher-order attributed tree transducers as a formal computational model for higher-order attribute grammars. The latter is a generalization of the classical concept of attribute grammars in the sense that during attribute evaluation, the input tree can be enlarged by inserting subtrees which were computed during attribute evaluation. We prove the universality of this formalism by showing that the class of functions described by higher-order attributed tree transducers coincides with the class of (partial) recursive tree functions.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s002240010018", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "34"
      }
    ], 
    "keywords": [
      "evaluation", 
      "function", 
      "transducer", 
      "class", 
      "computational model", 
      "model", 
      "classical concept", 
      "attribute evaluation", 
      "latter", 
      "concept", 
      "sense", 
      "coincide", 
      "trees", 
      "higher-order attribute grammars", 
      "generalization", 
      "paper", 
      "formal computational model", 
      "class of functions", 
      "universality", 
      "attribute grammars", 
      "grammar", 
      "subtrees", 
      "formalism", 
      "tree transducers", 
      "input trees", 
      "tree function"
    ], 
    "name": "The Universality of Higher-Order Attributed Tree Transducers", 
    "pagination": "45-75", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1042624052"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s002240010018"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s002240010018", 
      "https://app.dimensions.ai/details/publication/pub.1042624052"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-05-10T09:48", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_320.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s002240010018"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

105 TRIPLES      21 PREDICATES      55 URIs      44 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s002240010018 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 anzsrc-for:08
4 anzsrc-for:0802
5 anzsrc-for:0805
6 schema:author Nc4bbf1041c934c55a8ace78eab9538b0
7 schema:datePublished 2000-02
8 schema:datePublishedReg 2000-02-01
9 schema:description Abstract. In this paper we present higher-order attributed tree transducers as a formal computational model for higher-order attribute grammars. The latter is a generalization of the classical concept of attribute grammars in the sense that during attribute evaluation, the input tree can be enlarged by inserting subtrees which were computed during attribute evaluation. We prove the universality of this formalism by showing that the class of functions described by higher-order attributed tree transducers coincides with the class of (partial) recursive tree functions.
10 schema:genre article
11 schema:inLanguage en
12 schema:isAccessibleForFree false
13 schema:isPartOf N8b9af31444504302992a0f51e7fcb285
14 Nf5f02e92197d41a695a821a465159be7
15 sg:journal.1052098
16 schema:keywords attribute evaluation
17 attribute grammars
18 class
19 class of functions
20 classical concept
21 coincide
22 computational model
23 concept
24 evaluation
25 formal computational model
26 formalism
27 function
28 generalization
29 grammar
30 higher-order attribute grammars
31 input trees
32 latter
33 model
34 paper
35 sense
36 subtrees
37 transducer
38 tree function
39 tree transducers
40 trees
41 universality
42 schema:name The Universality of Higher-Order Attributed Tree Transducers
43 schema:pagination 45-75
44 schema:productId N45596cef51e04949bee3b813260f9795
45 N69f4007bb5fb48d88ce0a67b7ad61e7e
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042624052
47 https://doi.org/10.1007/s002240010018
48 schema:sdDatePublished 2022-05-10T09:48
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher N82dfaf43106245b585a9fd73185f5ac3
51 schema:url https://doi.org/10.1007/s002240010018
52 sgo:license sg:explorer/license/
53 sgo:sdDataset articles
54 rdf:type schema:ScholarlyArticle
55 N45596cef51e04949bee3b813260f9795 schema:name dimensions_id
56 schema:value pub.1042624052
57 rdf:type schema:PropertyValue
58 N4c6693120dd142fe9a82cc5a38036865 schema:affiliation grid-institutes:grid.5037.1
59 schema:familyName Noll
60 schema:givenName T.
61 rdf:type schema:Person
62 N69f4007bb5fb48d88ce0a67b7ad61e7e schema:name doi
63 schema:value 10.1007/s002240010018
64 rdf:type schema:PropertyValue
65 N82dfaf43106245b585a9fd73185f5ac3 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N8b9af31444504302992a0f51e7fcb285 schema:issueNumber 1
68 rdf:type schema:PublicationIssue
69 Nc4bbf1041c934c55a8ace78eab9538b0 rdf:first N4c6693120dd142fe9a82cc5a38036865
70 rdf:rest Ndb4e9311d4d64803b4421970b9306bf5
71 Ndb4e9311d4d64803b4421970b9306bf5 rdf:first sg:person.014562633673.93
72 rdf:rest rdf:nil
73 Nf5f02e92197d41a695a821a465159be7 schema:volumeNumber 34
74 rdf:type schema:PublicationVolume
75 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
76 schema:name Mathematical Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
79 schema:name Applied Mathematics
80 rdf:type schema:DefinedTerm
81 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
82 schema:name Information and Computing Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
85 schema:name Computation Theory and Mathematics
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0805 schema:inDefinedTermSet anzsrc-for:
88 schema:name Distributed Computing
89 rdf:type schema:DefinedTerm
90 sg:journal.1052098 schema:issn 1432-4350
91 1433-0490
92 schema:name Theory of Computing Systems
93 schema:publisher Springer Nature
94 rdf:type schema:Periodical
95 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.4488.0
96 schema:familyName Vogler
97 schema:givenName H.
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93
99 rdf:type schema:Person
100 grid-institutes:grid.4488.0 schema:alternateName Institut für Softwaretechnik I,vogler@inf.tu-dresden.de, Dresden University of Technology, D-01062 Dresden, Germany, DE
101 schema:name Institut für Softwaretechnik I,vogler@inf.tu-dresden.de, Dresden University of Technology, D-01062 Dresden, Germany, DE
102 rdf:type schema:Organization
103 grid-institutes:grid.5037.1 schema:alternateName Department of Teleinformatics, noll@it.kth.se, Royal Institute of Technology (KTH), Electrum 204, S-16440 Kista, Sweden, SE
104 schema:name Department of Teleinformatics, noll@it.kth.se, Royal Institute of Technology (KTH), Electrum 204, S-16440 Kista, Sweden, SE
105 rdf:type schema:Organization
 




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


...