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 N250255e8890b4a95992cb14ab8d632a6
    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 Na4c74525f779492193a0a161ffe299a6
    10 schema:genre chapter
    11 schema:inLanguage en
    12 schema:isAccessibleForFree true
    13 schema:isPartOf Nc782a91817b64fedb649fee146274662
    14 schema:name String Coding of Trees with Locality and Heritability
    15 schema:pagination 251-262
    16 schema:productId N74074751ce7743af80cef1c51b80a609
    17 N873fc9840dce4ec2b274a84c0462f6af
    18 Nb57b24f9b9424705a211f90e527a34a4
    19 schema:publisher Ndebe09e12d854439bfcfa0ed46740aad
    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 N6ae97b464bda43ed93e0e738763b926b
    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 N250255e8890b4a95992cb14ab8d632a6 rdf:first sg:person.010013323122.87
    30 rdf:rest Ncf742641da3f4029b7ccb69a892aa3e5
    31 N2b8c38dd2b5e4c48b05c5275b449aed1 schema:familyName Wang
    32 schema:givenName Lusheng
    33 rdf:type schema:Person
    34 N6ae97b464bda43ed93e0e738763b926b schema:name Springer Nature - SN SciGraph project
    35 rdf:type schema:Organization
    36 N74074751ce7743af80cef1c51b80a609 schema:name readcube_id
    37 schema:value e2dfe2f2b20799e7f9a45318c1e314f59f7e95257e4ebe798a79a4e2860116a2
    38 rdf:type schema:PropertyValue
    39 N873fc9840dce4ec2b274a84c0462f6af schema:name doi
    40 schema:value 10.1007/11533719_27
    41 rdf:type schema:PropertyValue
    42 Na4c74525f779492193a0a161ffe299a6 rdf:first N2b8c38dd2b5e4c48b05c5275b449aed1
    43 rdf:rest rdf:nil
    44 Nb57b24f9b9424705a211f90e527a34a4 schema:name dimensions_id
    45 schema:value pub.1047625411
    46 rdf:type schema:PropertyValue
    47 Nc782a91817b64fedb649fee146274662 schema:isbn 978-3-540-28061-3
    48 978-3-540-31806-4
    49 schema:name Computing and Combinatorics
    50 rdf:type schema:Book
    51 Ncf742641da3f4029b7ccb69a892aa3e5 rdf:first sg:person.011402427702.78
    52 rdf:rest rdf:nil
    53 Ndebe09e12d854439bfcfa0ed46740aad schema:location Berlin, Heidelberg
    54 schema:name Springer Berlin Heidelberg
    55 rdf:type schema:Organisation
    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)


    ...