Space-Efficient Algorithms for Longest Increasing Subsequence View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2019-01-22

AUTHORS

Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui

ABSTRACT

Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in Onlogn time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For n≤s≤n, we present algorithms that use Oslogn bits and O1s⋅n2⋅logn time for computing the length of a longest increasing subsequence, and O1s⋅n2⋅log2n time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space. More... »

PAGES

1-20

References to SciGraph publications

  • 2014. Depth-First Search Using $$O(n)$$ Bits in ALGORITHMS AND COMPUTATION
  • 2006-03. Finding longest increasing and common subsequences in streaming data in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • 2014. Space-Efficient Randomized Algorithms for K-SUM in ALGORITHMS - ESA 2014
  • 2013. Priority Queues and Sorting for Read-Only Data in THEORY AND APPLICATIONS OF MODELS OF COMPUTATION
  • 2017-07-01. A Time-Space Trade-Off for Triangulations of Points in the Plane in COMPUTING AND COMBINATORICS
  • 2015-12. On the monotonicity of a data stream in COMBINATORICA
  • 2014. Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem in ALGORITHMS - ESA 2014
  • 2007-01. Multi-Pass Geometric Algorithms in DISCRETE & COMPUTATIONAL GEOMETRY
  • 2017-07-01. Space-Efficient Algorithms for Maximum Cardinality Search, Stack BFS, Queue BFS and Applications in COMPUTING AND COMBINATORICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-018-09908-6

    DOI

    http://dx.doi.org/10.1007/s00224-018-09908-6

    DIMENSIONS

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


    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": "Yokohama City University", 
              "id": "https://www.grid.ac/institutes/grid.268441.d", 
              "name": [
                "Yokohama City University, Yokohama, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kiyomi", 
            "givenName": "Masashi", 
            "id": "sg:person.013720602760.16", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013720602760.16"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Nagoya University", 
              "id": "https://www.grid.ac/institutes/grid.27476.30", 
              "name": [
                "Nagoya University, Nagoya, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ono", 
            "givenName": "Hirotaka", 
            "id": "sg:person.014116577666.12", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014116577666.12"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Kumamoto University", 
              "id": "https://www.grid.ac/institutes/grid.274841.c", 
              "name": [
                "Kumamoto University, Kumamoto, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Otachi", 
            "givenName": "Yota", 
            "id": "sg:person.011320361517.81", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011320361517.81"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Kaiserslautern", 
              "id": "https://www.grid.ac/institutes/grid.7645.0", 
              "name": [
                "TU Kaiserslautern, Kaiserslautern, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Schweitzer", 
            "givenName": "Pascal", 
            "id": "sg:person.010731762606.52", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010731762606.52"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Electro-Communications", 
              "id": "https://www.grid.ac/institutes/grid.266298.1", 
              "name": [
                "The University of Electro-Communications, Chofu, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tarui", 
            "givenName": "Jun", 
            "id": "sg:person.015320365745.79", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015320365745.79"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1080/00207169708804607", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002651202"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(80)90061-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009542145"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0020-0190(00)00124-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011043950"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-38236-9_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014465390", 
              "https://doi.org/10.1007/978-3-642-38236-9_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(70)80006-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017051545"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(75)90103-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021903032"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(75)90103-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021903032"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-006-7125-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021984983", 
              "https://doi.org/10.1007/s10878-006-7125-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/800135.804426", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022133183"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/359581.359603", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028814342"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/129712.129772", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029080488"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-44777-2_67", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029101830", 
              "https://doi.org/10.1007/978-3-662-44777-2_67"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0273-0979-99-00796-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034536926"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00493-014-3035-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038128762", 
              "https://doi.org/10.1007/s00493-014-3035-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00454-006-1275-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039055275", 
              "https://doi.org/10.1007/s00454-006-1275-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00454-006-1275-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039055275", 
              "https://doi.org/10.1007/s00454-006-1275-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ic.2010.04.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042223934"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-13075-0_44", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044134367", 
              "https://doi.org/10.1007/978-3-319-13075-0_44"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-0000(87)90002-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048242766"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-44777-2_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053602367", 
              "https://doi.org/10.1007/978-3-662-44777-2_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0211022", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841638"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/090770801", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062856679"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1004036", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062858051"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1005107", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062858235"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.4153/cjm-1961-015-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1072264359"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/130942152", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1085284492"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611973105.122", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088801600"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-62389-4_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1090448511", 
              "https://doi.org/10.1007/978-3-319-62389-4_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-62389-4_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1090448511", 
              "https://doi.org/10.1007/978-3-319-62389-4_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-62389-4_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1090448565", 
              "https://doi.org/10.1007/978-3-319-62389-4_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-62389-4_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1090448565", 
              "https://doi.org/10.1007/978-3-319-62389-4_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1998.743455", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093256014"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9781139872003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098667853"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-01-22", 
        "datePublishedReg": "2019-01-22", 
        "description": "Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in Onlogn time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For n\u2264s\u2264n, we present algorithms that use Oslogn bits and O1s\u22c5n2\u22c5logn time for computing the length of a longest increasing subsequence, and O1s\u22c5n2\u22c5log2n time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00224-018-09908-6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.7523640", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.6819872", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.7537999", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.7537998", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "type": "Periodical"
          }
        ], 
        "name": "Space-Efficient Algorithms for Longest Increasing Subsequence", 
        "pagination": "1-20", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "9941f70b3acf6fd290454c153708c19d855b395d9e0b3415752a86b741af8157"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-018-09908-6"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1111607053"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-018-09908-6", 
          "https://app.dimensions.ai/details/publication/pub.1111607053"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T08:55", 
        "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/0000000325_0000000325/records_100778_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00224-018-09908-6"
      }
    ]
     

    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/s00224-018-09908-6'

    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/s00224-018-09908-6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-018-09908-6'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-018-09908-6'


     

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

    199 TRIPLES      21 PREDICATES      53 URIs      16 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-018-09908-6 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N86b10924b17347c78dd910bcc1fbc94a
    4 schema:citation sg:pub.10.1007/978-3-319-13075-0_44
    5 sg:pub.10.1007/978-3-319-62389-4_1
    6 sg:pub.10.1007/978-3-319-62389-4_8
    7 sg:pub.10.1007/978-3-642-38236-9_4
    8 sg:pub.10.1007/978-3-662-44777-2_24
    9 sg:pub.10.1007/978-3-662-44777-2_67
    10 sg:pub.10.1007/s00454-006-1275-6
    11 sg:pub.10.1007/s00493-014-3035-1
    12 sg:pub.10.1007/s10878-006-7125-x
    13 https://doi.org/10.1016/0012-365x(75)90103-x
    14 https://doi.org/10.1016/0022-0000(87)90002-x
    15 https://doi.org/10.1016/0304-3975(80)90061-4
    16 https://doi.org/10.1016/j.ic.2010.04.003
    17 https://doi.org/10.1016/s0020-0190(00)00124-1
    18 https://doi.org/10.1016/s0022-0000(70)80006-x
    19 https://doi.org/10.1017/cbo9781139872003
    20 https://doi.org/10.1080/00207169708804607
    21 https://doi.org/10.1090/s0273-0979-99-00796-x
    22 https://doi.org/10.1109/sfcs.1998.743455
    23 https://doi.org/10.1137/0211022
    24 https://doi.org/10.1137/090770801
    25 https://doi.org/10.1137/1.9781611973105.122
    26 https://doi.org/10.1137/1004036
    27 https://doi.org/10.1137/1005107
    28 https://doi.org/10.1137/130942152
    29 https://doi.org/10.1145/129712.129772
    30 https://doi.org/10.1145/359581.359603
    31 https://doi.org/10.1145/800135.804426
    32 https://doi.org/10.4153/cjm-1961-015-3
    33 schema:datePublished 2019-01-22
    34 schema:datePublishedReg 2019-01-22
    35 schema:description Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in Onlogn time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For n≤s≤n, we present algorithms that use Oslogn bits and O1s⋅n2⋅logn time for computing the length of a longest increasing subsequence, and O1s⋅n2⋅log2n time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.
    36 schema:genre research_article
    37 schema:inLanguage en
    38 schema:isAccessibleForFree true
    39 schema:isPartOf sg:journal.1052098
    40 schema:name Space-Efficient Algorithms for Longest Increasing Subsequence
    41 schema:pagination 1-20
    42 schema:productId N2d3d159c024e4be09552ba841d46c824
    43 N62bee7a758124e6eb9470be7aa2fc36b
    44 Ndd0316f15f794c2fa724ede978bbf6f3
    45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1111607053
    46 https://doi.org/10.1007/s00224-018-09908-6
    47 schema:sdDatePublished 2019-04-11T08:55
    48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    49 schema:sdPublisher N2a6e9e4d7c0b49dc83b5d1e3c8cd1c7c
    50 schema:url https://link.springer.com/10.1007%2Fs00224-018-09908-6
    51 sgo:license sg:explorer/license/
    52 sgo:sdDataset articles
    53 rdf:type schema:ScholarlyArticle
    54 N06d36c0736094bd389723552876df836 rdf:first sg:person.011320361517.81
    55 rdf:rest N0deef665723e4797b7c90b2b4dc85328
    56 N0deef665723e4797b7c90b2b4dc85328 rdf:first sg:person.010731762606.52
    57 rdf:rest N2f84f6af69044a80b0a8cc090b2b375b
    58 N2a6e9e4d7c0b49dc83b5d1e3c8cd1c7c schema:name Springer Nature - SN SciGraph project
    59 rdf:type schema:Organization
    60 N2d3d159c024e4be09552ba841d46c824 schema:name readcube_id
    61 schema:value 9941f70b3acf6fd290454c153708c19d855b395d9e0b3415752a86b741af8157
    62 rdf:type schema:PropertyValue
    63 N2f84f6af69044a80b0a8cc090b2b375b rdf:first sg:person.015320365745.79
    64 rdf:rest rdf:nil
    65 N62bee7a758124e6eb9470be7aa2fc36b schema:name dimensions_id
    66 schema:value pub.1111607053
    67 rdf:type schema:PropertyValue
    68 N86b10924b17347c78dd910bcc1fbc94a rdf:first sg:person.013720602760.16
    69 rdf:rest Nc3cc2e82f0f545e78bc02080c8235aa3
    70 Nc3cc2e82f0f545e78bc02080c8235aa3 rdf:first sg:person.014116577666.12
    71 rdf:rest N06d36c0736094bd389723552876df836
    72 Ndd0316f15f794c2fa724ede978bbf6f3 schema:name doi
    73 schema:value 10.1007/s00224-018-09908-6
    74 rdf:type schema:PropertyValue
    75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Information and Computing Sciences
    77 rdf:type schema:DefinedTerm
    78 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Computation Theory and Mathematics
    80 rdf:type schema:DefinedTerm
    81 sg:grant.6819872 http://pending.schema.org/fundedItem sg:pub.10.1007/s00224-018-09908-6
    82 rdf:type schema:MonetaryGrant
    83 sg:grant.7523640 http://pending.schema.org/fundedItem sg:pub.10.1007/s00224-018-09908-6
    84 rdf:type schema:MonetaryGrant
    85 sg:grant.7537998 http://pending.schema.org/fundedItem sg:pub.10.1007/s00224-018-09908-6
    86 rdf:type schema:MonetaryGrant
    87 sg:grant.7537999 http://pending.schema.org/fundedItem sg:pub.10.1007/s00224-018-09908-6
    88 rdf:type schema:MonetaryGrant
    89 sg:journal.1052098 schema:issn 1432-4350
    90 1433-0490
    91 schema:name Theory of Computing Systems
    92 rdf:type schema:Periodical
    93 sg:person.010731762606.52 schema:affiliation https://www.grid.ac/institutes/grid.7645.0
    94 schema:familyName Schweitzer
    95 schema:givenName Pascal
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010731762606.52
    97 rdf:type schema:Person
    98 sg:person.011320361517.81 schema:affiliation https://www.grid.ac/institutes/grid.274841.c
    99 schema:familyName Otachi
    100 schema:givenName Yota
    101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011320361517.81
    102 rdf:type schema:Person
    103 sg:person.013720602760.16 schema:affiliation https://www.grid.ac/institutes/grid.268441.d
    104 schema:familyName Kiyomi
    105 schema:givenName Masashi
    106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013720602760.16
    107 rdf:type schema:Person
    108 sg:person.014116577666.12 schema:affiliation https://www.grid.ac/institutes/grid.27476.30
    109 schema:familyName Ono
    110 schema:givenName Hirotaka
    111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014116577666.12
    112 rdf:type schema:Person
    113 sg:person.015320365745.79 schema:affiliation https://www.grid.ac/institutes/grid.266298.1
    114 schema:familyName Tarui
    115 schema:givenName Jun
    116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015320365745.79
    117 rdf:type schema:Person
    118 sg:pub.10.1007/978-3-319-13075-0_44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044134367
    119 https://doi.org/10.1007/978-3-319-13075-0_44
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/978-3-319-62389-4_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090448511
    122 https://doi.org/10.1007/978-3-319-62389-4_1
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/978-3-319-62389-4_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090448565
    125 https://doi.org/10.1007/978-3-319-62389-4_8
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/978-3-642-38236-9_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014465390
    128 https://doi.org/10.1007/978-3-642-38236-9_4
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/978-3-662-44777-2_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053602367
    131 https://doi.org/10.1007/978-3-662-44777-2_24
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/978-3-662-44777-2_67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029101830
    134 https://doi.org/10.1007/978-3-662-44777-2_67
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/s00454-006-1275-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039055275
    137 https://doi.org/10.1007/s00454-006-1275-6
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/s00493-014-3035-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038128762
    140 https://doi.org/10.1007/s00493-014-3035-1
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/s10878-006-7125-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1021984983
    143 https://doi.org/10.1007/s10878-006-7125-x
    144 rdf:type schema:CreativeWork
    145 https://doi.org/10.1016/0012-365x(75)90103-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1021903032
    146 rdf:type schema:CreativeWork
    147 https://doi.org/10.1016/0022-0000(87)90002-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1048242766
    148 rdf:type schema:CreativeWork
    149 https://doi.org/10.1016/0304-3975(80)90061-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009542145
    150 rdf:type schema:CreativeWork
    151 https://doi.org/10.1016/j.ic.2010.04.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042223934
    152 rdf:type schema:CreativeWork
    153 https://doi.org/10.1016/s0020-0190(00)00124-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011043950
    154 rdf:type schema:CreativeWork
    155 https://doi.org/10.1016/s0022-0000(70)80006-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1017051545
    156 rdf:type schema:CreativeWork
    157 https://doi.org/10.1017/cbo9781139872003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098667853
    158 rdf:type schema:CreativeWork
    159 https://doi.org/10.1080/00207169708804607 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002651202
    160 rdf:type schema:CreativeWork
    161 https://doi.org/10.1090/s0273-0979-99-00796-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1034536926
    162 rdf:type schema:CreativeWork
    163 https://doi.org/10.1109/sfcs.1998.743455 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093256014
    164 rdf:type schema:CreativeWork
    165 https://doi.org/10.1137/0211022 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841638
    166 rdf:type schema:CreativeWork
    167 https://doi.org/10.1137/090770801 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062856679
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1137/1.9781611973105.122 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801600
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1137/1004036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062858051
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1137/1005107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062858235
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1137/130942152 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085284492
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1145/129712.129772 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029080488
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1145/359581.359603 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028814342
    180 rdf:type schema:CreativeWork
    181 https://doi.org/10.1145/800135.804426 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022133183
    182 rdf:type schema:CreativeWork
    183 https://doi.org/10.4153/cjm-1961-015-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072264359
    184 rdf:type schema:CreativeWork
    185 https://www.grid.ac/institutes/grid.266298.1 schema:alternateName University of Electro-Communications
    186 schema:name The University of Electro-Communications, Chofu, Japan
    187 rdf:type schema:Organization
    188 https://www.grid.ac/institutes/grid.268441.d schema:alternateName Yokohama City University
    189 schema:name Yokohama City University, Yokohama, Japan
    190 rdf:type schema:Organization
    191 https://www.grid.ac/institutes/grid.27476.30 schema:alternateName Nagoya University
    192 schema:name Nagoya University, Nagoya, Japan
    193 rdf:type schema:Organization
    194 https://www.grid.ac/institutes/grid.274841.c schema:alternateName Kumamoto University
    195 schema:name Kumamoto University, Kumamoto, Japan
    196 rdf:type schema:Organization
    197 https://www.grid.ac/institutes/grid.7645.0 schema:alternateName University of Kaiserslautern
    198 schema:name TU Kaiserslautern, Kaiserslautern, Germany
    199 rdf:type schema:Organization
     




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


    ...