Longest Common Substring with Approximately k Mismatches View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-02-16

AUTHORS

Tomasz Kociumaka, Jakub Radoszewski, Tatiana Starikovskaya

ABSTRACT

In the longest common substring problem, we are given two strings of length n and must find a substring of maximal length that occurs in both strings. It is well known that the problem can be solved in linear time, but the solution is not robust and can vary greatly when the input strings are changed even by one character. To circumvent this, Leimeister and Morgenstern introduced the problem of the longest common substring with k mismatches. Lately, this problem has received a lot of attention in the literature. In this paper, we first show a conditional lower bound based on the SETH hypothesis implying that there is little hope to improve existing solutions. We then introduce a new but closely related problem of the longest common substring with approximately k mismatches and use locality-sensitive hashing to show that it admits a solution with strongly subquadratic running time. We also apply these results to obtain a strongly subquadratic-time 2-approximation algorithm for the longest common substring with k mismatches problem and show conditional hardness of improving its approximation ratio. More... »

PAGES

1-20

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-019-00548-x

DOI

http://dx.doi.org/10.1007/s00453-019-00548-x

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Warsaw", 
          "id": "https://www.grid.ac/institutes/grid.12847.38", 
          "name": [
            "Institute of Informatics, University of Warsaw, Warsaw, Poland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kociumaka", 
        "givenName": "Tomasz", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Warsaw", 
          "id": "https://www.grid.ac/institutes/grid.12847.38", 
          "name": [
            "Institute of Informatics, University of Warsaw, Warsaw, Poland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Radoszewski", 
        "givenName": "Jakub", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "\u00c9cole Normale Sup\u00e9rieure", 
          "id": "https://www.grid.ac/institutes/grid.5607.4", 
          "name": [
            "DIENS, \u00c9cole Normale Sup\u00e9rieure, PSL University, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Starikovskaya", 
        "givenName": "Tatiana", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1134/s0032946011010030", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002454916", 
          "https://doi.org/10.1134/s0032946011010030"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-44777-2_50", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002950586", 
          "https://doi.org/10.1007/978-3-662-44777-2_50"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2015.03.006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004211246"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1004947649", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-21275-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004947649", 
          "https://doi.org/10.1007/978-3-319-21275-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-21275-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004947649", 
          "https://doi.org/10.1007/978-3-319-21275-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jda.2010.08.004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007417655"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jcss.2001.1774", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010461930"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/btu331", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013421163"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-2836(05)80360-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013618994"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-28332-1_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017630051", 
          "https://doi.org/10.1007/978-3-642-28332-1_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(87)90042-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018747311"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1109557.1109690", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021628824"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0025-5718-2011-02542-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021856335"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2015.03.003", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029068939"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(86)90178-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031788419"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(86)90178-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031788419"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jda.2013.06.003", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039193405"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-79709-8_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041636462", 
          "https://doi.org/10.1007/978-3-540-79709-8_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2005.09.023", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042662432"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-38905-4_22", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047582941", 
          "https://doi.org/10.1007/978-3-642-38905-4_22"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-56024-6_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048804175", 
          "https://doi.org/10.1007/3-540-56024-6_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2746539.2746568", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050949269"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jcss.2000.1727", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051281103"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/01621459.1963.10500830", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1058299773"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1089/cmb.2015.0235", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059246344"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0213024", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841758"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/090779759", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062856985"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539798347177", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880290"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1147/rd.312.0249", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063181514"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4007/annals.2004.160.781", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1071866875"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/swat.1973.13", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086215622"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/focs.2009.11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094106091"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511574931", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098674485"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-89929-9_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1103421934", 
          "https://doi.org/10.1007/978-3-319-89929-9_14"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-02-16", 
    "datePublishedReg": "2019-02-16", 
    "description": "In the longest common substring problem, we are given two strings of length n and must find a substring of maximal length that occurs in both strings. It is well known that the problem can be solved in linear time, but the solution is not robust and can vary greatly when the input strings are changed even by one character. To circumvent this, Leimeister and Morgenstern introduced the problem of the longest common substring with k mismatches. Lately, this problem has received a lot of attention in the literature. In this paper, we first show a conditional lower bound based on the SETH hypothesis implying that there is little hope to improve existing solutions. We then introduce a new but closely related problem of the longest common substring with approximately k mismatches and use locality-sensitive hashing to show that it admits a solution with strongly subquadratic running time. We also apply these results to obtain a strongly subquadratic-time 2-approximation algorithm for the longest common substring with k mismatches problem and show conditional hardness of improving its approximation ratio.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-019-00548-x", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }
    ], 
    "name": "Longest Common Substring with Approximately k Mismatches", 
    "pagination": "1-20", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1112218736"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-019-00548-x"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b37375fdcec599427f098660a7759a404f6231e199254e4e80f42a7055bf7019"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-019-00548-x", 
      "https://app.dimensions.ai/details/publication/pub.1112218736"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-16T06:23", 
    "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/0000000377_0000000377/records_106822_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00453-019-00548-x"
  }
]
 

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/s00453-019-00548-x'

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/s00453-019-00548-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-019-00548-x'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-019-00548-x'


 

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

175 TRIPLES      21 PREDICATES      57 URIs      16 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-019-00548-x schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Nbfe1b9d7bd3e47229cfef7d1432122f9
4 schema:citation sg:pub.10.1007/3-540-56024-6_19
5 sg:pub.10.1007/978-3-319-21275-3
6 sg:pub.10.1007/978-3-319-89929-9_14
7 sg:pub.10.1007/978-3-540-79709-8_10
8 sg:pub.10.1007/978-3-642-28332-1_11
9 sg:pub.10.1007/978-3-642-38905-4_22
10 sg:pub.10.1007/978-3-662-44777-2_50
11 sg:pub.10.1134/s0032946011010030
12 https://app.dimensions.ai/details/publication/pub.1004947649
13 https://doi.org/10.1006/jcss.2000.1727
14 https://doi.org/10.1006/jcss.2001.1774
15 https://doi.org/10.1016/0304-3975(86)90178-7
16 https://doi.org/10.1016/0304-3975(87)90042-9
17 https://doi.org/10.1016/j.ipl.2015.03.003
18 https://doi.org/10.1016/j.ipl.2015.03.006
19 https://doi.org/10.1016/j.jda.2010.08.004
20 https://doi.org/10.1016/j.jda.2013.06.003
21 https://doi.org/10.1016/j.tcs.2005.09.023
22 https://doi.org/10.1016/s0022-2836(05)80360-2
23 https://doi.org/10.1017/cbo9780511574931
24 https://doi.org/10.1080/01621459.1963.10500830
25 https://doi.org/10.1089/cmb.2015.0235
26 https://doi.org/10.1090/s0025-5718-2011-02542-1
27 https://doi.org/10.1093/bioinformatics/btu331
28 https://doi.org/10.1109/focs.2009.11
29 https://doi.org/10.1109/swat.1973.13
30 https://doi.org/10.1137/0213024
31 https://doi.org/10.1137/090779759
32 https://doi.org/10.1137/s0097539798347177
33 https://doi.org/10.1145/1109557.1109690
34 https://doi.org/10.1145/2746539.2746568
35 https://doi.org/10.1147/rd.312.0249
36 https://doi.org/10.4007/annals.2004.160.781
37 schema:datePublished 2019-02-16
38 schema:datePublishedReg 2019-02-16
39 schema:description In the longest common substring problem, we are given two strings of length n and must find a substring of maximal length that occurs in both strings. It is well known that the problem can be solved in linear time, but the solution is not robust and can vary greatly when the input strings are changed even by one character. To circumvent this, Leimeister and Morgenstern introduced the problem of the longest common substring with k mismatches. Lately, this problem has received a lot of attention in the literature. In this paper, we first show a conditional lower bound based on the SETH hypothesis implying that there is little hope to improve existing solutions. We then introduce a new but closely related problem of the longest common substring with approximately k mismatches and use locality-sensitive hashing to show that it admits a solution with strongly subquadratic running time. We also apply these results to obtain a strongly subquadratic-time 2-approximation algorithm for the longest common substring with k mismatches problem and show conditional hardness of improving its approximation ratio.
40 schema:genre research_article
41 schema:inLanguage en
42 schema:isAccessibleForFree false
43 schema:isPartOf sg:journal.1047644
44 schema:name Longest Common Substring with Approximately k Mismatches
45 schema:pagination 1-20
46 schema:productId N0948ec6058154f74b9762c5ff916bc2d
47 N10856a98fc15401a80b0074f91187ac8
48 N36e0490127014a9184ab5da84fbec567
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112218736
50 https://doi.org/10.1007/s00453-019-00548-x
51 schema:sdDatePublished 2019-04-16T06:23
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N053e5fb7fbe9401e81955d5ec0dd65b5
54 schema:url https://link.springer.com/10.1007%2Fs00453-019-00548-x
55 sgo:license sg:explorer/license/
56 sgo:sdDataset articles
57 rdf:type schema:ScholarlyArticle
58 N053e5fb7fbe9401e81955d5ec0dd65b5 schema:name Springer Nature - SN SciGraph project
59 rdf:type schema:Organization
60 N0948ec6058154f74b9762c5ff916bc2d schema:name readcube_id
61 schema:value b37375fdcec599427f098660a7759a404f6231e199254e4e80f42a7055bf7019
62 rdf:type schema:PropertyValue
63 N10856a98fc15401a80b0074f91187ac8 schema:name dimensions_id
64 schema:value pub.1112218736
65 rdf:type schema:PropertyValue
66 N183c2db05f544d8390c6dc39c5f6773a rdf:first N608b00f971da4d48be20158e4f4a3bbd
67 rdf:rest rdf:nil
68 N183c5b6c6dde42828bcf0932a67f4365 rdf:first Ne8a212a8ab024723bec673bb2a26cc0f
69 rdf:rest N183c2db05f544d8390c6dc39c5f6773a
70 N36e0490127014a9184ab5da84fbec567 schema:name doi
71 schema:value 10.1007/s00453-019-00548-x
72 rdf:type schema:PropertyValue
73 N608b00f971da4d48be20158e4f4a3bbd schema:affiliation https://www.grid.ac/institutes/grid.5607.4
74 schema:familyName Starikovskaya
75 schema:givenName Tatiana
76 rdf:type schema:Person
77 Nb80237a7c6664ed8a11c7bba6c8a97c3 schema:affiliation https://www.grid.ac/institutes/grid.12847.38
78 schema:familyName Kociumaka
79 schema:givenName Tomasz
80 rdf:type schema:Person
81 Nbfe1b9d7bd3e47229cfef7d1432122f9 rdf:first Nb80237a7c6664ed8a11c7bba6c8a97c3
82 rdf:rest N183c5b6c6dde42828bcf0932a67f4365
83 Ne8a212a8ab024723bec673bb2a26cc0f schema:affiliation https://www.grid.ac/institutes/grid.12847.38
84 schema:familyName Radoszewski
85 schema:givenName Jakub
86 rdf:type schema:Person
87 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
88 schema:name Mathematical Sciences
89 rdf:type schema:DefinedTerm
90 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
91 schema:name Numerical and Computational Mathematics
92 rdf:type schema:DefinedTerm
93 sg:journal.1047644 schema:issn 0178-4617
94 1432-0541
95 schema:name Algorithmica
96 rdf:type schema:Periodical
97 sg:pub.10.1007/3-540-56024-6_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048804175
98 https://doi.org/10.1007/3-540-56024-6_19
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/978-3-319-21275-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004947649
101 https://doi.org/10.1007/978-3-319-21275-3
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/978-3-319-89929-9_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103421934
104 https://doi.org/10.1007/978-3-319-89929-9_14
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/978-3-540-79709-8_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041636462
107 https://doi.org/10.1007/978-3-540-79709-8_10
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/978-3-642-28332-1_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017630051
110 https://doi.org/10.1007/978-3-642-28332-1_11
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/978-3-642-38905-4_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047582941
113 https://doi.org/10.1007/978-3-642-38905-4_22
114 rdf:type schema:CreativeWork
115 sg:pub.10.1007/978-3-662-44777-2_50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002950586
116 https://doi.org/10.1007/978-3-662-44777-2_50
117 rdf:type schema:CreativeWork
118 sg:pub.10.1134/s0032946011010030 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002454916
119 https://doi.org/10.1134/s0032946011010030
120 rdf:type schema:CreativeWork
121 https://app.dimensions.ai/details/publication/pub.1004947649 schema:CreativeWork
122 https://doi.org/10.1006/jcss.2000.1727 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051281103
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1006/jcss.2001.1774 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010461930
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1016/0304-3975(86)90178-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031788419
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1016/0304-3975(87)90042-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018747311
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1016/j.ipl.2015.03.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029068939
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1016/j.ipl.2015.03.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004211246
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1016/j.jda.2010.08.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007417655
135 rdf:type schema:CreativeWork
136 https://doi.org/10.1016/j.jda.2013.06.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039193405
137 rdf:type schema:CreativeWork
138 https://doi.org/10.1016/j.tcs.2005.09.023 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042662432
139 rdf:type schema:CreativeWork
140 https://doi.org/10.1016/s0022-2836(05)80360-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013618994
141 rdf:type schema:CreativeWork
142 https://doi.org/10.1017/cbo9780511574931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098674485
143 rdf:type schema:CreativeWork
144 https://doi.org/10.1080/01621459.1963.10500830 schema:sameAs https://app.dimensions.ai/details/publication/pub.1058299773
145 rdf:type schema:CreativeWork
146 https://doi.org/10.1089/cmb.2015.0235 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059246344
147 rdf:type schema:CreativeWork
148 https://doi.org/10.1090/s0025-5718-2011-02542-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021856335
149 rdf:type schema:CreativeWork
150 https://doi.org/10.1093/bioinformatics/btu331 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013421163
151 rdf:type schema:CreativeWork
152 https://doi.org/10.1109/focs.2009.11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094106091
153 rdf:type schema:CreativeWork
154 https://doi.org/10.1109/swat.1973.13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086215622
155 rdf:type schema:CreativeWork
156 https://doi.org/10.1137/0213024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841758
157 rdf:type schema:CreativeWork
158 https://doi.org/10.1137/090779759 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062856985
159 rdf:type schema:CreativeWork
160 https://doi.org/10.1137/s0097539798347177 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880290
161 rdf:type schema:CreativeWork
162 https://doi.org/10.1145/1109557.1109690 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021628824
163 rdf:type schema:CreativeWork
164 https://doi.org/10.1145/2746539.2746568 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050949269
165 rdf:type schema:CreativeWork
166 https://doi.org/10.1147/rd.312.0249 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063181514
167 rdf:type schema:CreativeWork
168 https://doi.org/10.4007/annals.2004.160.781 schema:sameAs https://app.dimensions.ai/details/publication/pub.1071866875
169 rdf:type schema:CreativeWork
170 https://www.grid.ac/institutes/grid.12847.38 schema:alternateName University of Warsaw
171 schema:name Institute of Informatics, University of Warsaw, Warsaw, Poland
172 rdf:type schema:Organization
173 https://www.grid.ac/institutes/grid.5607.4 schema:alternateName École Normale Supérieure
174 schema:name DIENS, École Normale Supérieure, PSL University, Paris, France
175 rdf:type schema:Organization
 




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


...