Synthesized and inherited functions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1994-05

AUTHORS

Armin Kühnemann, Heiko Vogler

ABSTRACT

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. More... »

PAGES

431-477

References to SciGraph publications

  • 1987-12. Graph expressions and graph rewritings in THEORY OF COMPUTING SYSTEMS
  • <error retrieving object. in <ERROR RETRIEVING OBJECT
  • 1968-06. Semantics of context-free languages in THEORY OF COMPUTING SYSTEMS
  • 1979. The Denotational Description of Programming Languages, An Introduction in NONE
  • 1992-02. Context-free hypergraph grammars have the same term-generating power as attribute grammars in ACTA INFORMATICA
  • 1989. The Synthesizer Generator, A System for Constructing Language-Based Editors in NONE
  • 1988-05. Composition and evaluation of attribute coupled grammars in ACTA INFORMATICA
  • 1987. May we introduce to you: Hyperedge replacement in GRAPH-GRAMMARS AND THEIR APPLICATION TO COMPUTER SCIENCE
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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"
          }, 
          {
            "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

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




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


    ...