String Coding of Trees with Locality and Heritability View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Saverio Caminiti , Rossella Petreschi

ABSTRACT

We consider the problem of coding labelled trees by means of strings of vertex labels and we present a general scheme to define bijective codes based on the transformation of a tree into a functional digraph. Looking at the fields in which codes for labelled trees are utilized, we see that the properties of locality and heritability are required and that codes like the well known Prüfer code do not satisfy these properties. We present a general scheme for generating codes based on the construction of functional digraphs. We prove that using this scheme, locality and heritability are satisfied as a direct function of the similarity between the topology of the functional digraph and that of the original tree. Moreover, we also show that the efficiency of our method depends on the transformation of the tree into a functional digraph. Finally we show how it is possible to fit three known codes into our scheme, obtaining maximum efficiency and high locality and heritability. More... »

PAGES

251-262

References to SciGraph publications

  • 2004. A Unified Approach to Coding Labeled Trees in LATIN 2004: THEORETICAL INFORMATICS
  • Book

    TITLE

    Computing and Combinatorics

    ISBN

    978-3-540-28061-3
    978-3-540-31806-4

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/11533719_27

    DOI

    http://dx.doi.org/10.1007/11533719_27

    DIMENSIONS

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


    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/0501", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Ecological Applications", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/05", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Environmental Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento di Informatica, Universit\u00e0 degli Studi di Roma \u201cLa Sapienza\u201d, Via Salaria 113, 00198, Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Caminiti", 
            "givenName": "Saverio", 
            "id": "sg:person.010013323122.87", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010013323122.87"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento di Informatica, Universit\u00e0 degli Studi di Roma \u201cLa Sapienza\u201d, Via Salaria 113, 00198, Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Petreschi", 
            "givenName": "Rossella", 
            "id": "sg:person.011402427702.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1002/(sici)1097-0037(199709)30:2<91::aid-net3>3.0.co;2-f", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013908963"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24698-5_38", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043716409", 
              "https://doi.org/10.1007/978-3-540-24698-5_38"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24698-5_38", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043716409", 
              "https://doi.org/10.1007/978-3-540-24698-5_38"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2005", 
        "datePublishedReg": "2005-01-01", 
        "description": "We consider the problem of coding labelled trees by means of strings of vertex labels and we present a general scheme to define bijective codes based on the transformation of a tree into a functional digraph. Looking at the fields in which codes for labelled trees are utilized, we see that the properties of locality and heritability are required and that codes like the well known Pr\u00fcfer code do not satisfy these properties. We present a general scheme for generating codes based on the construction of functional digraphs. We prove that using this scheme, locality and heritability are satisfied as a direct function of the similarity between the topology of the functional digraph and that of the original tree. Moreover, we also show that the efficiency of our method depends on the transformation of the tree into a functional digraph. Finally we show how it is possible to fit three known codes into our scheme, obtaining maximum efficiency and high locality and heritability.", 
        "editor": [
          {
            "familyName": "Wang", 
            "givenName": "Lusheng", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/11533719_27", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-28061-3", 
            "978-3-540-31806-4"
          ], 
          "name": "Computing and Combinatorics", 
          "type": "Book"
        }, 
        "name": "String Coding of Trees with Locality and Heritability", 
        "pagination": "251-262", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1047625411"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11533719_27"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "e2dfe2f2b20799e7f9a45318c1e314f59f7e95257e4ebe798a79a4e2860116a2"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11533719_27", 
          "https://app.dimensions.ai/details/publication/pub.1047625411"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:27", 
        "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/0000000363_0000000363/records_70061_00000002.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F11533719_27"
      }
    ]
     

    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/11533719_27'

    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/11533719_27'

    Turtle is a human-readable linked data format.

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

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

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


     

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

    79 TRIPLES      23 PREDICATES      29 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11533719_27 schema:about anzsrc-for:05
    2 anzsrc-for:0501
    3 schema:author Nc93ca964e68b443fa55d006e5b2f0544
    4 schema:citation sg:pub.10.1007/978-3-540-24698-5_38
    5 https://doi.org/10.1002/(sici)1097-0037(199709)30:2<91::aid-net3>3.0.co;2-f
    6 schema:datePublished 2005
    7 schema:datePublishedReg 2005-01-01
    8 schema:description We consider the problem of coding labelled trees by means of strings of vertex labels and we present a general scheme to define bijective codes based on the transformation of a tree into a functional digraph. Looking at the fields in which codes for labelled trees are utilized, we see that the properties of locality and heritability are required and that codes like the well known Prüfer code do not satisfy these properties. We present a general scheme for generating codes based on the construction of functional digraphs. We prove that using this scheme, locality and heritability are satisfied as a direct function of the similarity between the topology of the functional digraph and that of the original tree. Moreover, we also show that the efficiency of our method depends on the transformation of the tree into a functional digraph. Finally we show how it is possible to fit three known codes into our scheme, obtaining maximum efficiency and high locality and heritability.
    9 schema:editor N2d0f51fde79d411b8987e3a310dc8b5e
    10 schema:genre chapter
    11 schema:inLanguage en
    12 schema:isAccessibleForFree true
    13 schema:isPartOf N2ca88025996148c4b5f95cc5fcbd7495
    14 schema:name String Coding of Trees with Locality and Heritability
    15 schema:pagination 251-262
    16 schema:productId N79ed04de16d9471989f8c7bf0a4e2795
    17 N7debf4f3e92d4e8cb29a3a752ef623cf
    18 N96079bcebd39402cb97245e37b4fa7ef
    19 schema:publisher N68541f2919984fa18031e93deca1389c
    20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047625411
    21 https://doi.org/10.1007/11533719_27
    22 schema:sdDatePublished 2019-04-16T08:27
    23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    24 schema:sdPublisher N43f7c25b78f34d449c5947790dbc778c
    25 schema:url https://link.springer.com/10.1007%2F11533719_27
    26 sgo:license sg:explorer/license/
    27 sgo:sdDataset chapters
    28 rdf:type schema:Chapter
    29 N2ca88025996148c4b5f95cc5fcbd7495 schema:isbn 978-3-540-28061-3
    30 978-3-540-31806-4
    31 schema:name Computing and Combinatorics
    32 rdf:type schema:Book
    33 N2d0f51fde79d411b8987e3a310dc8b5e rdf:first Nb5a65eb1c84d46b78f112d2303b250c4
    34 rdf:rest rdf:nil
    35 N43f7c25b78f34d449c5947790dbc778c schema:name Springer Nature - SN SciGraph project
    36 rdf:type schema:Organization
    37 N58d27ad967ce4f81be87040856a5f98d rdf:first sg:person.011402427702.78
    38 rdf:rest rdf:nil
    39 N68541f2919984fa18031e93deca1389c schema:location Berlin, Heidelberg
    40 schema:name Springer Berlin Heidelberg
    41 rdf:type schema:Organisation
    42 N79ed04de16d9471989f8c7bf0a4e2795 schema:name dimensions_id
    43 schema:value pub.1047625411
    44 rdf:type schema:PropertyValue
    45 N7debf4f3e92d4e8cb29a3a752ef623cf schema:name doi
    46 schema:value 10.1007/11533719_27
    47 rdf:type schema:PropertyValue
    48 N96079bcebd39402cb97245e37b4fa7ef schema:name readcube_id
    49 schema:value e2dfe2f2b20799e7f9a45318c1e314f59f7e95257e4ebe798a79a4e2860116a2
    50 rdf:type schema:PropertyValue
    51 Nb5a65eb1c84d46b78f112d2303b250c4 schema:familyName Wang
    52 schema:givenName Lusheng
    53 rdf:type schema:Person
    54 Nc93ca964e68b443fa55d006e5b2f0544 rdf:first sg:person.010013323122.87
    55 rdf:rest N58d27ad967ce4f81be87040856a5f98d
    56 anzsrc-for:05 schema:inDefinedTermSet anzsrc-for:
    57 schema:name Environmental Sciences
    58 rdf:type schema:DefinedTerm
    59 anzsrc-for:0501 schema:inDefinedTermSet anzsrc-for:
    60 schema:name Ecological Applications
    61 rdf:type schema:DefinedTerm
    62 sg:person.010013323122.87 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    63 schema:familyName Caminiti
    64 schema:givenName Saverio
    65 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010013323122.87
    66 rdf:type schema:Person
    67 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    68 schema:familyName Petreschi
    69 schema:givenName Rossella
    70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
    71 rdf:type schema:Person
    72 sg:pub.10.1007/978-3-540-24698-5_38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043716409
    73 https://doi.org/10.1007/978-3-540-24698-5_38
    74 rdf:type schema:CreativeWork
    75 https://doi.org/10.1002/(sici)1097-0037(199709)30:2<91::aid-net3>3.0.co;2-f schema:sameAs https://app.dimensions.ai/details/publication/pub.1013908963
    76 rdf:type schema:CreativeWork
    77 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    78 schema:name Dipartimento di Informatica, Università degli Studi di Roma “La Sapienza”, Via Salaria 113, 00198, Roma, Italy
    79 rdf:type schema:Organization
     




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


    ...