Graph grammars and tree transducers View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1994

AUTHORS

Joost Engelfriet

ABSTRACT

Regular tree grammars can be used to generate graphs, by generating expressions that denote graphs. Top-down and bottom-up tree transducers are a tool for proving properties of such graph generating tree grammars.

PAGES

15-36

References to SciGraph publications

  • 1989-09. Metatheorems for decision problems on hyperedge replacement graph languages in ACTA INFORMATICA
  • 1976-12. Top-down tree transducers with regular look-ahead in MATHEMATICAL SYSTEMS THEORY
  • 1970-09. Mappings and grammars on trees in MATHEMATICAL SYSTEMS THEORY
  • 1987-12. Graph expressions and graph rewritings in MATHEMATICAL SYSTEMS THEORY
  • Book

    TITLE

    Trees in Algebra and Programming — CAAP'94

    ISBN

    3-540-57879-X

    Author Affiliations

    Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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", 
        "author": [
          {
            "affiliation": {
              "alternateName": "Leiden University", 
              "id": "https://www.grid.ac/institutes/grid.5132.5", 
              "name": [
                "Department of Computer Science, Leiden University, P.O.Box 9512, 2300\u00a0RA Leiden, The Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Engelfriet", 
            "givenName": "Joost", 
            "id": "sg:person.014574236321.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0304-3975(92)90148-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001565841"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(90)90106-r", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005357398"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(91)90387-h", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008128114"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(91)90387-h", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008128114"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(93)90064-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008541341"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0019-9958(67)90353-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010914398"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(81)90013-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012596998"
            ], 
            "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/bf01692060", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013326091", 
              "https://doi.org/10.1007/bf01692060"
            ], 
            "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": "https://doi.org/10.1016/0022-0000(93)90004-g", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013811435"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01683280", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014989626", 
              "https://doi.org/10.1007/bf01683280"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01683280", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014989626", 
              "https://doi.org/10.1007/bf01683280"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(91)90174-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015370594"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(93)90106-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019996634"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0890-5401(90)90043-h", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027180474"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00288976", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033100693", 
              "https://doi.org/10.1007/bf00288976"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00288976", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033100693", 
              "https://doi.org/10.1007/bf00288976"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0890-5401(90)90038-j", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033751887"
            ], 
            "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/bf01695769", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033919759", 
              "https://doi.org/10.1007/bf01695769"
            ], 
            "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": "https://doi.org/10.1016/0304-3975(87)90102-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038921884"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/151261.151268", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051499465"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(93)90354-v", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052642045"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1994", 
        "datePublishedReg": "1994-01-01", 
        "description": "Regular tree grammars can be used to generate graphs, by generating expressions that denote graphs. Top-down and bottom-up tree transducers are a tool for proving properties of such graph generating tree grammars.", 
        "editor": [
          {
            "familyName": "Tison", 
            "givenName": "Sophie", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/bfb0017471", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "3-540-57879-X"
          ], 
          "name": "Trees in Algebra and Programming \u2014 CAAP'94", 
          "type": "Book"
        }, 
        "name": "Graph grammars and tree transducers", 
        "pagination": "15-36", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bfb0017471"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "449f0e70b6e4b8348e574d71335d19380cf9a762ce21e25f9a218d462114481d"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1014404258"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin/Heidelberg", 
          "name": "Springer-Verlag", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/bfb0017471", 
          "https://app.dimensions.ai/details/publication/pub.1014404258"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T20:04", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8687_00000252.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/BFb0017471"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    114 TRIPLES      22 PREDICATES      43 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bfb0017471 schema:author N33084a25fc364546ab7d0ff37a5c193a
    2 schema:citation sg:pub.10.1007/bf00288976
    3 sg:pub.10.1007/bf01683280
    4 sg:pub.10.1007/bf01692060
    5 sg:pub.10.1007/bf01695769
    6 https://doi.org/10.1016/0022-0000(93)90004-g
    7 https://doi.org/10.1016/0166-218x(81)90013-5
    8 https://doi.org/10.1016/0166-218x(93)90106-x
    9 https://doi.org/10.1016/0304-3975(87)90102-2
    10 https://doi.org/10.1016/0304-3975(90)90106-r
    11 https://doi.org/10.1016/0304-3975(91)90174-z
    12 https://doi.org/10.1016/0304-3975(91)90387-h
    13 https://doi.org/10.1016/0304-3975(92)90148-9
    14 https://doi.org/10.1016/0304-3975(93)90064-z
    15 https://doi.org/10.1016/0304-3975(93)90354-v
    16 https://doi.org/10.1016/0890-5401(90)90038-j
    17 https://doi.org/10.1016/0890-5401(90)90043-h
    18 https://doi.org/10.1016/s0019-9958(67)90353-1
    19 https://doi.org/10.1145/151261.151268
    20 schema:datePublished 1994
    21 schema:datePublishedReg 1994-01-01
    22 schema:description Regular tree grammars can be used to generate graphs, by generating expressions that denote graphs. Top-down and bottom-up tree transducers are a tool for proving properties of such graph generating tree grammars.
    23 schema:editor N186767881af0489a9b77724e3b516d8c
    24 schema:genre chapter
    25 schema:inLanguage en
    26 schema:isAccessibleForFree false
    27 schema:isPartOf N0de13c18db0a41cba4db4725f34d99f6
    28 schema:name Graph grammars and tree transducers
    29 schema:pagination 15-36
    30 schema:productId N0c420c3fe2b34065bf31b93922f3f291
    31 N4dfdf9d246f3420584b7b89332e4b65c
    32 N4eb0790cb29742b38cf8587c3aabef0b
    33 schema:publisher Nf5f8facb15394952a4b7fc750b7390bc
    34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014404258
    35 https://doi.org/10.1007/bfb0017471
    36 schema:sdDatePublished 2019-04-15T20:04
    37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    38 schema:sdPublisher N5056b17e04f843caa0afdeca3a62c196
    39 schema:url http://link.springer.com/10.1007/BFb0017471
    40 sgo:license sg:explorer/license/
    41 sgo:sdDataset chapters
    42 rdf:type schema:Chapter
    43 N0c420c3fe2b34065bf31b93922f3f291 schema:name doi
    44 schema:value 10.1007/bfb0017471
    45 rdf:type schema:PropertyValue
    46 N0de13c18db0a41cba4db4725f34d99f6 schema:isbn 3-540-57879-X
    47 schema:name Trees in Algebra and Programming — CAAP'94
    48 rdf:type schema:Book
    49 N186767881af0489a9b77724e3b516d8c rdf:first N9ba8360785b54228ad63b25d73a2ac51
    50 rdf:rest rdf:nil
    51 N33084a25fc364546ab7d0ff37a5c193a rdf:first sg:person.014574236321.39
    52 rdf:rest rdf:nil
    53 N4dfdf9d246f3420584b7b89332e4b65c schema:name readcube_id
    54 schema:value 449f0e70b6e4b8348e574d71335d19380cf9a762ce21e25f9a218d462114481d
    55 rdf:type schema:PropertyValue
    56 N4eb0790cb29742b38cf8587c3aabef0b schema:name dimensions_id
    57 schema:value pub.1014404258
    58 rdf:type schema:PropertyValue
    59 N5056b17e04f843caa0afdeca3a62c196 schema:name Springer Nature - SN SciGraph project
    60 rdf:type schema:Organization
    61 N9ba8360785b54228ad63b25d73a2ac51 schema:familyName Tison
    62 schema:givenName Sophie
    63 rdf:type schema:Person
    64 Nf5f8facb15394952a4b7fc750b7390bc schema:location Berlin/Heidelberg
    65 schema:name Springer-Verlag
    66 rdf:type schema:Organisation
    67 sg:person.014574236321.39 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
    68 schema:familyName Engelfriet
    69 schema:givenName Joost
    70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
    71 rdf:type schema:Person
    72 sg:pub.10.1007/bf00288976 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033100693
    73 https://doi.org/10.1007/bf00288976
    74 rdf:type schema:CreativeWork
    75 sg:pub.10.1007/bf01683280 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014989626
    76 https://doi.org/10.1007/bf01683280
    77 rdf:type schema:CreativeWork
    78 sg:pub.10.1007/bf01692060 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013326091
    79 https://doi.org/10.1007/bf01692060
    80 rdf:type schema:CreativeWork
    81 sg:pub.10.1007/bf01695769 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033919759
    82 https://doi.org/10.1007/bf01695769
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1016/0022-0000(93)90004-g schema:sameAs https://app.dimensions.ai/details/publication/pub.1013811435
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1016/0166-218x(81)90013-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012596998
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1016/0166-218x(93)90106-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1019996634
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1016/0304-3975(87)90102-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038921884
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1016/0304-3975(90)90106-r schema:sameAs https://app.dimensions.ai/details/publication/pub.1005357398
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1016/0304-3975(91)90174-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1015370594
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1016/0304-3975(91)90387-h schema:sameAs https://app.dimensions.ai/details/publication/pub.1008128114
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1016/0304-3975(92)90148-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001565841
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/0304-3975(93)90064-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1008541341
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/0304-3975(93)90354-v schema:sameAs https://app.dimensions.ai/details/publication/pub.1052642045
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1016/0890-5401(90)90038-j schema:sameAs https://app.dimensions.ai/details/publication/pub.1033751887
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1016/0890-5401(90)90043-h schema:sameAs https://app.dimensions.ai/details/publication/pub.1027180474
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1016/s0019-9958(67)90353-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010914398
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1145/151261.151268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051499465
    111 rdf:type schema:CreativeWork
    112 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
    113 schema:name Department of Computer Science, Leiden University, P.O.Box 9512, 2300 RA Leiden, The Netherlands
    114 rdf:type schema:Organization
     




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


    ...