A constrained edit distance between unordered labeled trees View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1996-03

AUTHORS

Kaizhong Zhang

ABSTRACT

This paper considers the problem of computing a constrained edit distance between unordered labeled trees. The problem of approximate unordered tree matching is also considered. We present dynamic programming algorithms solving these problems in sequential timeO(|T1|×|T2|×(deg(T1)+deg(T2))× log2(deg(T1)+deg(T2))). Our previous result shows that computing the edit distance between unordered labeled trees is NP-complete. More... »

PAGES

205-222

References to SciGraph publications

  • 1991-08. Object representation and recognition using mathematical morphology model in JOURNAL OF SYSTEMS INTEGRATION
  • 1991. The tree inclusion problem in TAPSOFT '91
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Western University", 
              "id": "https://www.grid.ac/institutes/grid.39381.30", 
              "name": [
                "Department of Computer Science, University of Western Ontario, N6A 5B7, London, Ontario, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zhang", 
            "givenName": "Kaizhong", 
            "id": "sg:person.015001674137.24", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015001674137.24"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-53982-4_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016370055", 
              "https://doi.org/10.1007/3-540-53982-4_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/322139.322143", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016458504"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(92)90136-j", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016602097"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(85)90023-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022034071"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(89)90010-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026116948"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2116/analsci.3.23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029290832"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02426925", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032098295", 
              "https://doi.org/10.1007/bf02426925"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02426925", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032098295", 
              "https://doi.org/10.1007/bf02426925"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(80)90016-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034676227"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(94)90062-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035113856"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jagm.1994.1003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041557324"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/bioinformatics/6.4.309", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059413968"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/34.23111", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061155852"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/69.298173", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061213312"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0218082", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842181"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0218001488000157", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062950606"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1992.267823", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086343424"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611970265", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098556619"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1996-03", 
        "datePublishedReg": "1996-03-01", 
        "description": "This paper considers the problem of computing a constrained edit distance between unordered labeled trees. The problem of approximate unordered tree matching is also considered. We present dynamic programming algorithms solving these problems in sequential timeO(|T1|\u00d7|T2|\u00d7(deg(T1)+deg(T2))\u00d7 log2(deg(T1)+deg(T2))). Our previous result shows that computing the edit distance between unordered labeled trees is NP-complete.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf01975866", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "15"
          }
        ], 
        "name": "A constrained edit distance between unordered labeled trees", 
        "pagination": "205-222", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "a12b5b88f3a69ba78269b93d2e0629d85dc046882cab1d5e2700bae71b2e28ee"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01975866"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1033832980"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01975866", 
          "https://app.dimensions.ai/details/publication/pub.1033832980"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T11:24", 
        "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/0000000355_0000000355/records_53022_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF01975866"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    114 TRIPLES      21 PREDICATES      44 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01975866 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N86904c3fe89c4fdc8b38b781b8747296
    4 schema:citation sg:pub.10.1007/3-540-53982-4_12
    5 sg:pub.10.1007/bf02426925
    6 https://doi.org/10.1006/jagm.1994.1003
    7 https://doi.org/10.1016/0020-0190(92)90136-j
    8 https://doi.org/10.1016/0020-0190(94)90062-0
    9 https://doi.org/10.1016/0196-6774(80)90016-4
    10 https://doi.org/10.1016/0196-6774(85)90023-9
    11 https://doi.org/10.1016/0196-6774(89)90010-2
    12 https://doi.org/10.1093/bioinformatics/6.4.309
    13 https://doi.org/10.1109/34.23111
    14 https://doi.org/10.1109/69.298173
    15 https://doi.org/10.1109/sfcs.1992.267823
    16 https://doi.org/10.1137/0218082
    17 https://doi.org/10.1137/1.9781611970265
    18 https://doi.org/10.1142/s0218001488000157
    19 https://doi.org/10.1145/322139.322143
    20 https://doi.org/10.2116/analsci.3.23
    21 schema:datePublished 1996-03
    22 schema:datePublishedReg 1996-03-01
    23 schema:description This paper considers the problem of computing a constrained edit distance between unordered labeled trees. The problem of approximate unordered tree matching is also considered. We present dynamic programming algorithms solving these problems in sequential timeO(|T1|×|T2|×(deg(T1)+deg(T2))× log2(deg(T1)+deg(T2))). Our previous result shows that computing the edit distance between unordered labeled trees is NP-complete.
    24 schema:genre research_article
    25 schema:inLanguage en
    26 schema:isAccessibleForFree false
    27 schema:isPartOf Na09720e8448346d2b01673201dcb2d3c
    28 Nee48c504ce614a5ba8eb9643d4942296
    29 sg:journal.1047644
    30 schema:name A constrained edit distance between unordered labeled trees
    31 schema:pagination 205-222
    32 schema:productId Nb733a75eed7f4d8998466a3c35364757
    33 Ndf3733c5155e4f7cb087ad7d04fbb1e9
    34 Ne8f11046f8b743b3a2c74bfd20c6af89
    35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033832980
    36 https://doi.org/10.1007/bf01975866
    37 schema:sdDatePublished 2019-04-11T11:24
    38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    39 schema:sdPublisher N141a9ad833ac422288a284c36f1778b8
    40 schema:url http://link.springer.com/10.1007/BF01975866
    41 sgo:license sg:explorer/license/
    42 sgo:sdDataset articles
    43 rdf:type schema:ScholarlyArticle
    44 N141a9ad833ac422288a284c36f1778b8 schema:name Springer Nature - SN SciGraph project
    45 rdf:type schema:Organization
    46 N86904c3fe89c4fdc8b38b781b8747296 rdf:first sg:person.015001674137.24
    47 rdf:rest rdf:nil
    48 Na09720e8448346d2b01673201dcb2d3c schema:volumeNumber 15
    49 rdf:type schema:PublicationVolume
    50 Nb733a75eed7f4d8998466a3c35364757 schema:name doi
    51 schema:value 10.1007/bf01975866
    52 rdf:type schema:PropertyValue
    53 Ndf3733c5155e4f7cb087ad7d04fbb1e9 schema:name dimensions_id
    54 schema:value pub.1033832980
    55 rdf:type schema:PropertyValue
    56 Ne8f11046f8b743b3a2c74bfd20c6af89 schema:name readcube_id
    57 schema:value a12b5b88f3a69ba78269b93d2e0629d85dc046882cab1d5e2700bae71b2e28ee
    58 rdf:type schema:PropertyValue
    59 Nee48c504ce614a5ba8eb9643d4942296 schema:issueNumber 3
    60 rdf:type schema:PublicationIssue
    61 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Information and Computing Sciences
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Computation Theory and Mathematics
    66 rdf:type schema:DefinedTerm
    67 sg:journal.1047644 schema:issn 0178-4617
    68 1432-0541
    69 schema:name Algorithmica
    70 rdf:type schema:Periodical
    71 sg:person.015001674137.24 schema:affiliation https://www.grid.ac/institutes/grid.39381.30
    72 schema:familyName Zhang
    73 schema:givenName Kaizhong
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015001674137.24
    75 rdf:type schema:Person
    76 sg:pub.10.1007/3-540-53982-4_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016370055
    77 https://doi.org/10.1007/3-540-53982-4_12
    78 rdf:type schema:CreativeWork
    79 sg:pub.10.1007/bf02426925 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032098295
    80 https://doi.org/10.1007/bf02426925
    81 rdf:type schema:CreativeWork
    82 https://doi.org/10.1006/jagm.1994.1003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041557324
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1016/0020-0190(92)90136-j schema:sameAs https://app.dimensions.ai/details/publication/pub.1016602097
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1016/0020-0190(94)90062-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035113856
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1016/0196-6774(80)90016-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034676227
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1016/0196-6774(85)90023-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022034071
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1016/0196-6774(89)90010-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026116948
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1093/bioinformatics/6.4.309 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059413968
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1109/34.23111 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061155852
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1109/69.298173 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061213312
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1109/sfcs.1992.267823 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086343424
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1137/0218082 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842181
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1137/1.9781611970265 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098556619
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1142/s0218001488000157 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062950606
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1145/322139.322143 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016458504
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.2116/analsci.3.23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029290832
    111 rdf:type schema:CreativeWork
    112 https://www.grid.ac/institutes/grid.39381.30 schema:alternateName Western University
    113 schema:name Department of Computer Science, University of Western Ontario, N6A 5B7, London, Ontario, Canada
    114 rdf:type schema:Organization
     




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


    ...