1994-05
AUTHORS ABSTRACTIn this paper we introduce a new formal model for the concept of syntaxdirected semantics, calledmacro attributed tree transducer (for short: mat tree transducer). This model is based on (noncircular) attributed tree transducers and on macro tree transducers. In the first type of transducer, semantic values are computed by means of meaning names called synthesized attributes, and by means of context names called inherited attributes. Both, synthesized and inherited attributes represent basic semantic values. In the second type of transducer, semantic values are computed by meaning names only which are called states. However, in order to have a means of handling context information, states represent functions over semantic values. The new model integrates attributed tree transducers and macro tree transducers by allowing both, meaning names and context names to represent functions over semantic values. In analogy to the terminology of attributed tree transducers, we call such meaning names and context names also synthesized functions and inherited functions, respectively.We present an inductive characterization of the tree transformation computed by an mat tree transducer. We prove that mat tree transducers are more powerful than both, attributed tree transducers and macro tree transducers. We characterize mat tree transducers by the two-fold composition of attributed tree transducers. This characterization has three consequences: (1) the height of output trees of mat tree transducers is bounded exponentially in the size of the input tree, (2) the composition hierarchy of mat tree transducers is strict, and (3) mat tree transducers are closed under right-composition with top-down tree transducers, but not under left-composition. Moreover, we prove that the addition of inherited attributes does not increase the computational power of macro tree transducers. More... »
PAGES431-477
http://scigraph.springernature.com/pub.10.1007/bf01178667
DOIhttp://dx.doi.org/10.1007/bf01178667
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1009419920
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"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0803",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computer Software",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Data Format",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Abteilung Theoretische Informatik, Universit\u00e4t Ulm, Oberer Eselsberg, D-89069, Ulm, Germany",
"id": "http://www.grid.ac/institutes/grid.6582.9",
"name": [
"Abteilung Theoretische Informatik, Universit\u00e4t Ulm, Oberer Eselsberg, D-89069, Ulm, Germany"
],
"type": "Organization"
},
"familyName": "K\u00fchnemann",
"givenName": "Armin",
"id": "sg:person.015633306630.74",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015633306630.74"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Abteilung Theoretische Informatik, Universit\u00e4t Ulm, Oberer Eselsberg, D-89069, Ulm, Germany",
"id": "http://www.grid.ac/institutes/grid.6582.9",
"name": [
"Abteilung Theoretische Informatik, Universit\u00e4t Ulm, Oberer Eselsberg, D-89069, Ulm, Germany"
],
"type": "Organization"
},
"familyName": "Vogler",
"givenName": "Heiko",
"id": "sg:person.014562633673.93",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/bf01178504",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1019908786",
"https://doi.org/10.1007/bf01178504"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-18771-5_41",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038756659",
"https://doi.org/10.1007/3-540-18771-5_41"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01692060",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013326091",
"https://doi.org/10.1007/bf01692060"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4613-9623-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018007832",
"https://doi.org/10.1007/978-1-4613-9623-9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02737108",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039434342",
"https://doi.org/10.1007/bf02737108"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01695769",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033919759",
"https://doi.org/10.1007/bf01695769"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01692511",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1025480202",
"https://doi.org/10.1007/bf01692511"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4612-6228-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035549662",
"https://doi.org/10.1007/978-1-4612-6228-2"
],
"type": "CreativeWork"
}
],
"datePublished": "1994-05",
"datePublishedReg": "1994-05-01",
"description": "In this paper we introduce a new formal model for the concept of syntaxdirected semantics, calledmacro attributed tree transducer (for short: mat tree transducer). This model is based on (noncircular) attributed tree transducers and on macro tree transducers. In the first type of transducer, semantic values are computed by means of meaning names called synthesized attributes, and by means of context names called inherited attributes. Both, synthesized and inherited attributes represent basic semantic values. In the second type of transducer, semantic values are computed by meaning names only which are called states. However, in order to have a means of handling context information, states represent functions over semantic values. The new model integrates attributed tree transducers and macro tree transducers by allowing both, meaning names and context names to represent functions over semantic values. In analogy to the terminology of attributed tree transducers, we call such meaning names and context names also synthesized functions and inherited functions, respectively.We present an inductive characterization of the tree transformation computed by an mat tree transducer. We prove that mat tree transducers are more powerful than both, attributed tree transducers and macro tree transducers. We characterize mat tree transducers by the two-fold composition of attributed tree transducers. This characterization has three consequences: (1) the height of output trees of mat tree transducers is bounded exponentially in the size of the input tree, (2) the composition hierarchy of mat tree transducers is strict, and (3) mat tree transducers are closed under right-composition with top-down tree transducers, but not under left-composition. Moreover, we prove that the addition of inherited attributes does not increase the computational power of macro tree transducers.",
"genre": "article",
"id": "sg:pub.10.1007/bf01178667",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1133515",
"issn": [
"0001-5903",
"1432-0525"
],
"name": "Acta Informatica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "5",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "31"
}
],
"keywords": [
"paper",
"new formal model",
"formal model",
"model",
"concept",
"semantics",
"tree transducers",
"transducer",
"macro tree transducers",
"first type",
"types",
"semantic value",
"values",
"means",
"name",
"attributes",
"second type",
"state",
"order",
"context information",
"information",
"function",
"new model",
"analogy",
"terminology",
"inductive characterization",
"characterization",
"tree transformations",
"transformation",
"composition",
"consequences",
"height",
"output tree",
"trees",
"size",
"input trees",
"composition hierarchy",
"hierarchy",
"addition",
"computational power",
"power"
],
"name": "Synthesized and inherited functions",
"pagination": "431-477",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1009419920"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/bf01178667"
]
}
],
"sameAs": [
"https://doi.org/10.1007/bf01178667",
"https://app.dimensions.ai/details/publication/pub.1009419920"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:19",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_258.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/bf01178667"
}
]
Download the RDF metadata as: json-ld nt turtle xml License info
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/bf01178667'
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/bf01178667'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01178667'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01178667'
This table displays all metadata directly associated to this object as RDF triples.
146 TRIPLES
22 PREDICATES
77 URIs
59 LITERALS
6 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/bf01178667 | schema:about | anzsrc-for:08 |
2 | ″ | ″ | anzsrc-for:0802 |
3 | ″ | ″ | anzsrc-for:0803 |
4 | ″ | ″ | anzsrc-for:0804 |
5 | ″ | schema:author | N79852dc1b28946a3bb668f2b20acc612 |
6 | ″ | schema:citation | sg:pub.10.1007/3-540-18771-5_41 |
7 | ″ | ″ | sg:pub.10.1007/978-1-4612-6228-2 |
8 | ″ | ″ | sg:pub.10.1007/978-1-4613-9623-9 |
9 | ″ | ″ | sg:pub.10.1007/bf01178504 |
10 | ″ | ″ | sg:pub.10.1007/bf01692060 |
11 | ″ | ″ | sg:pub.10.1007/bf01692511 |
12 | ″ | ″ | sg:pub.10.1007/bf01695769 |
13 | ″ | ″ | sg:pub.10.1007/bf02737108 |
14 | ″ | schema:datePublished | 1994-05 |
15 | ″ | schema:datePublishedReg | 1994-05-01 |
16 | ″ | schema:description | In this paper we introduce a new formal model for the concept of syntaxdirected semantics, calledmacro attributed tree transducer (for short: mat tree transducer). This model is based on (noncircular) attributed tree transducers and on macro tree transducers. In the first type of transducer, semantic values are computed by means of meaning names called synthesized attributes, and by means of context names called inherited attributes. Both, synthesized and inherited attributes represent basic semantic values. In the second type of transducer, semantic values are computed by meaning names only which are called states. However, in order to have a means of handling context information, states represent functions over semantic values. The new model integrates attributed tree transducers and macro tree transducers by allowing both, meaning names and context names to represent functions over semantic values. In analogy to the terminology of attributed tree transducers, we call such meaning names and context names also synthesized functions and inherited functions, respectively.We present an inductive characterization of the tree transformation computed by an mat tree transducer. We prove that mat tree transducers are more powerful than both, attributed tree transducers and macro tree transducers. We characterize mat tree transducers by the two-fold composition of attributed tree transducers. This characterization has three consequences: (1) the height of output trees of mat tree transducers is bounded exponentially in the size of the input tree, (2) the composition hierarchy of mat tree transducers is strict, and (3) mat tree transducers are closed under right-composition with top-down tree transducers, but not under left-composition. Moreover, we prove that the addition of inherited attributes does not increase the computational power of macro tree transducers. |
17 | ″ | schema:genre | article |
18 | ″ | schema:inLanguage | en |
19 | ″ | schema:isAccessibleForFree | false |
20 | ″ | schema:isPartOf | N045e1a13590e492aa0f7ba7549ed2337 |
21 | ″ | ″ | N643b2d165aee4a5786dc7f7514d9e851 |
22 | ″ | ″ | sg:journal.1133515 |
23 | ″ | schema:keywords | addition |
24 | ″ | ″ | analogy |
25 | ″ | ″ | attributes |
26 | ″ | ″ | characterization |
27 | ″ | ″ | composition |
28 | ″ | ″ | composition hierarchy |
29 | ″ | ″ | computational power |
30 | ″ | ″ | concept |
31 | ″ | ″ | consequences |
32 | ″ | ″ | context information |
33 | ″ | ″ | first type |
34 | ″ | ″ | formal model |
35 | ″ | ″ | function |
36 | ″ | ″ | height |
37 | ″ | ″ | hierarchy |
38 | ″ | ″ | inductive characterization |
39 | ″ | ″ | information |
40 | ″ | ″ | input trees |
41 | ″ | ″ | macro tree transducers |
42 | ″ | ″ | means |
43 | ″ | ″ | model |
44 | ″ | ″ | name |
45 | ″ | ″ | new formal model |
46 | ″ | ″ | new model |
47 | ″ | ″ | order |
48 | ″ | ″ | output tree |
49 | ″ | ″ | paper |
50 | ″ | ″ | power |
51 | ″ | ″ | second type |
52 | ″ | ″ | semantic value |
53 | ″ | ″ | semantics |
54 | ″ | ″ | size |
55 | ″ | ″ | state |
56 | ″ | ″ | terminology |
57 | ″ | ″ | transducer |
58 | ″ | ″ | transformation |
59 | ″ | ″ | tree transducers |
60 | ″ | ″ | tree transformations |
61 | ″ | ″ | trees |
62 | ″ | ″ | types |
63 | ″ | ″ | values |
64 | ″ | schema:name | Synthesized and inherited functions |
65 | ″ | schema:pagination | 431-477 |
66 | ″ | schema:productId | Nb0db42ec4aa54221b978244205675ba0 |
67 | ″ | ″ | Nbbb1818a481e49479cb97cfe0980d5d1 |
68 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1009419920 |
69 | ″ | ″ | https://doi.org/10.1007/bf01178667 |
70 | ″ | schema:sdDatePublished | 2022-05-20T07:19 |
71 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
72 | ″ | schema:sdPublisher | Nb9d720c609c342a49efaec837cc52255 |
73 | ″ | schema:url | https://doi.org/10.1007/bf01178667 |
74 | ″ | sgo:license | sg:explorer/license/ |
75 | ″ | sgo:sdDataset | articles |
76 | ″ | rdf:type | schema:ScholarlyArticle |
77 | N045e1a13590e492aa0f7ba7549ed2337 | schema:volumeNumber | 31 |
78 | ″ | rdf:type | schema:PublicationVolume |
79 | N0823b04c9e7340c28d949e0a12e416db | rdf:first | sg:person.014562633673.93 |
80 | ″ | rdf:rest | rdf:nil |
81 | N643b2d165aee4a5786dc7f7514d9e851 | schema:issueNumber | 5 |
82 | ″ | rdf:type | schema:PublicationIssue |
83 | N79852dc1b28946a3bb668f2b20acc612 | rdf:first | sg:person.015633306630.74 |
84 | ″ | rdf:rest | N0823b04c9e7340c28d949e0a12e416db |
85 | Nb0db42ec4aa54221b978244205675ba0 | schema:name | dimensions_id |
86 | ″ | schema:value | pub.1009419920 |
87 | ″ | rdf:type | schema:PropertyValue |
88 | Nb9d720c609c342a49efaec837cc52255 | schema:name | Springer Nature - SN SciGraph project |
89 | ″ | rdf:type | schema:Organization |
90 | Nbbb1818a481e49479cb97cfe0980d5d1 | schema:name | doi |
91 | ″ | schema:value | 10.1007/bf01178667 |
92 | ″ | rdf:type | schema:PropertyValue |
93 | anzsrc-for:08 | schema:inDefinedTermSet | anzsrc-for: |
94 | ″ | schema:name | Information and Computing Sciences |
95 | ″ | rdf:type | schema:DefinedTerm |
96 | anzsrc-for:0802 | schema:inDefinedTermSet | anzsrc-for: |
97 | ″ | schema:name | Computation Theory and Mathematics |
98 | ″ | rdf:type | schema:DefinedTerm |
99 | anzsrc-for:0803 | schema:inDefinedTermSet | anzsrc-for: |
100 | ″ | schema:name | Computer Software |
101 | ″ | rdf:type | schema:DefinedTerm |
102 | anzsrc-for:0804 | schema:inDefinedTermSet | anzsrc-for: |
103 | ″ | schema:name | Data Format |
104 | ″ | rdf:type | schema:DefinedTerm |
105 | sg:journal.1133515 | schema:issn | 0001-5903 |
106 | ″ | ″ | 1432-0525 |
107 | ″ | schema:name | Acta Informatica |
108 | ″ | schema:publisher | Springer Nature |
109 | ″ | rdf:type | schema:Periodical |
110 | sg:person.014562633673.93 | schema:affiliation | grid-institutes:grid.6582.9 |
111 | ″ | schema:familyName | Vogler |
112 | ″ | schema:givenName | Heiko |
113 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93 |
114 | ″ | rdf:type | schema:Person |
115 | sg:person.015633306630.74 | schema:affiliation | grid-institutes:grid.6582.9 |
116 | ″ | schema:familyName | Kühnemann |
117 | ″ | schema:givenName | Armin |
118 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015633306630.74 |
119 | ″ | rdf:type | schema:Person |
120 | sg:pub.10.1007/3-540-18771-5_41 | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1038756659 |
121 | ″ | ″ | https://doi.org/10.1007/3-540-18771-5_41 |
122 | ″ | rdf:type | schema:CreativeWork |
123 | sg:pub.10.1007/978-1-4612-6228-2 | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1035549662 |
124 | ″ | ″ | https://doi.org/10.1007/978-1-4612-6228-2 |
125 | ″ | rdf:type | schema:CreativeWork |
126 | sg:pub.10.1007/978-1-4613-9623-9 | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1018007832 |
127 | ″ | ″ | https://doi.org/10.1007/978-1-4613-9623-9 |
128 | ″ | rdf:type | schema:CreativeWork |
129 | sg:pub.10.1007/bf01178504 | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1019908786 |
130 | ″ | ″ | https://doi.org/10.1007/bf01178504 |
131 | ″ | rdf:type | schema:CreativeWork |
132 | sg:pub.10.1007/bf01692060 | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1013326091 |
133 | ″ | ″ | https://doi.org/10.1007/bf01692060 |
134 | ″ | rdf:type | schema:CreativeWork |
135 | sg:pub.10.1007/bf01692511 | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1025480202 |
136 | ″ | ″ | https://doi.org/10.1007/bf01692511 |
137 | ″ | rdf:type | schema:CreativeWork |
138 | sg:pub.10.1007/bf01695769 | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1033919759 |
139 | ″ | ″ | https://doi.org/10.1007/bf01695769 |
140 | ″ | rdf:type | schema:CreativeWork |
141 | sg:pub.10.1007/bf02737108 | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1039434342 |
142 | ″ | ″ | https://doi.org/10.1007/bf02737108 |
143 | ″ | rdf:type | schema:CreativeWork |
144 | grid-institutes:grid.6582.9 | schema:alternateName | Abteilung Theoretische Informatik, Universität Ulm, Oberer Eselsberg, D-89069, Ulm, Germany |
145 | ″ | schema:name | Abteilung Theoretische Informatik, Universität Ulm, Oberer Eselsberg, D-89069, Ulm, Germany |
146 | ″ | rdf:type | schema:Organization |