Knapsack in Graph Groups View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-01

AUTHORS

Markus Lohrey, Georg Zetzsche

ABSTRACT

It is shown that the knapsack problem, which was introduced by Myasnikov et al. for arbitrary finitely generated groups, can be solved in NP for every graph group. This result even holds if the group elements are represented in a compressed form by so called straight-line programs, which generalizes the classical NP-completeness result of the integer knapsack problem. If group elements are represented explicitly by words over the generators, then knapsack for a graph group belongs to the class LogCFL (a subclass of P) if the graph group can be built up from the trivial group using the operations of free product and direct product with ℤ. In all other cases, the knapsack problem is NP-complete. More... »

PAGES

192-246

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00224-017-9808-3

DOI

http://dx.doi.org/10.1007/s00224-017-9808-3

DIMENSIONS

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


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": "University of Siegen", 
          "id": "https://www.grid.ac/institutes/grid.5836.8", 
          "name": [
            "Universit\u00e4t Siegen, Siegen, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lohrey", 
        "givenName": "Markus", 
        "id": "sg:person.015611460437.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015611460437.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Laboratoire Sp\u00e9cification et V\u00e9rification", 
          "id": "https://www.grid.ac/institutes/grid.464035.0", 
          "name": [
            "LSV, CNRS & ENS Paris-Saclay, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zetzsche", 
        "givenName": "Georg", 
        "id": "sg:person.014551676263.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014551676263.38"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/j.jsc.2015.05.006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000757901"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jsc.2015.05.006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000757901"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jsc.2015.05.006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000757901"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jsc.2015.05.006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000757901"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321250.321254", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001877493"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0890-5401(89)90051-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002448602"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/322358.322373", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005188359"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4684-2001-2_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007977430", 
          "https://doi.org/10.1007/978-1-4684-2001-2_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-03927-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010704788", 
          "https://doi.org/10.1007/978-3-662-03927-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-03927-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010704788", 
          "https://doi.org/10.1007/978-3-662-03927-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4939-0748-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017532757", 
          "https://doi.org/10.1007/978-1-4939-0748-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4939-0748-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017532757", 
          "https://doi.org/10.1007/978-1-4939-0748-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-21398-9_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018165371", 
          "https://doi.org/10.1007/978-3-319-21398-9_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2009.06.005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018736955"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-53904-2_94", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018800611", 
          "https://doi.org/10.1007/3-540-53904-2_94"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/322276.322287", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020447697"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02088289", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020923430", 
          "https://doi.org/10.1007/bf02088289"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02088289", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020923430", 
          "https://doi.org/10.1007/bf02088289"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(02)00025-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022572190"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(02)00025-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022572190"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9939-1978-0500555-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024056895"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(95)00017-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026732294"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9939-1965-0172274-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027030070"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-48340-3_8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030203570", 
          "https://doi.org/10.1007/3-540-48340-3_8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-74510-5_26", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031210348", 
          "https://doi.org/10.1007/978-3-540-74510-5_26"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-74510-5_26", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031210348", 
          "https://doi.org/10.1007/978-3-540-74510-5_26"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0025-5718-2014-02880-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031890506"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.aam.2005.08.009", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032366230"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1515/gcc-2012-0016", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032881373"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/322077.322083", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039489555"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/00927870802243580", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039759685"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s002220050168", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047153124", 
          "https://doi.org/10.1007/s002220050168"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jsc.2015.11.009", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048617341"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.aim.2010.01.011", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049624204"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/258533.258590", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051965740"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jalgebra.2007.08.025", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052736790"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.2005.850116", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061650556"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0202025", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841213"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0218196706003001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062961263"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0218196706003372", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062961298"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0218196708004548", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062961416"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1307/mmj/1030132408", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064976885"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2140/agt.2004.4.439", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069057445"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/3597196", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1070385308"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.3934/era.2009.16.44", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1071738731"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jsc.2017.03.007", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084092369"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/conm/677/13625", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1087152886"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511804090", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098662846"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1098909602", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-53031-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109702479", 
          "https://doi.org/10.1007/3-540-53031-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-53031-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109702479", 
          "https://doi.org/10.1007/3-540-53031-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-53031-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109702479", 
          "https://doi.org/10.1007/3-540-53031-2"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-01", 
    "datePublishedReg": "2018-01-01", 
    "description": "It is shown that the knapsack problem, which was introduced by Myasnikov et al. for arbitrary finitely generated groups, can be solved in NP for every graph group. This result even holds if the group elements are represented in a compressed form by so called straight-line programs, which generalizes the classical NP-completeness result of the integer knapsack problem. If group elements are represented explicitly by words over the generators, then knapsack for a graph group belongs to the class LogCFL (a subclass of P) if the graph group can be built up from the trivial group using the operations of free product and direct product with \u2124. In all other cases, the knapsack problem is NP-complete.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00224-017-9808-3", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "62"
      }
    ], 
    "name": "Knapsack in Graph Groups", 
    "pagination": "192-246", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "396f6cb632f67e4a9bd84bf2258b55d63dace682da63f498d9fdc0c9fc05116e"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00224-017-9808-3"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1091596501"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00224-017-9808-3", 
      "https://app.dimensions.ai/details/publication/pub.1091596501"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T18:32", 
    "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/0000000001_0000000264/records_8675_00000601.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs00224-017-9808-3"
  }
]
 

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-017-9808-3'

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-017-9808-3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-017-9808-3'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-017-9808-3'


 

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

206 TRIPLES      21 PREDICATES      69 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00224-017-9808-3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N992a901b13ed4e52a58de9156ad7a865
4 schema:citation sg:pub.10.1007/3-540-48340-3_8
5 sg:pub.10.1007/3-540-53031-2
6 sg:pub.10.1007/3-540-53904-2_94
7 sg:pub.10.1007/978-1-4684-2001-2_9
8 sg:pub.10.1007/978-1-4939-0748-9
9 sg:pub.10.1007/978-3-319-21398-9_19
10 sg:pub.10.1007/978-3-540-74510-5_26
11 sg:pub.10.1007/978-3-662-03927-4
12 sg:pub.10.1007/bf02088289
13 sg:pub.10.1007/s002220050168
14 https://app.dimensions.ai/details/publication/pub.1098909602
15 https://doi.org/10.1016/0020-0190(95)00017-7
16 https://doi.org/10.1016/0890-5401(89)90051-5
17 https://doi.org/10.1016/j.aam.2005.08.009
18 https://doi.org/10.1016/j.aim.2010.01.011
19 https://doi.org/10.1016/j.ipl.2009.06.005
20 https://doi.org/10.1016/j.jalgebra.2007.08.025
21 https://doi.org/10.1016/j.jsc.2015.05.006
22 https://doi.org/10.1016/j.jsc.2015.11.009
23 https://doi.org/10.1016/j.jsc.2017.03.007
24 https://doi.org/10.1016/s0022-0000(02)00025-9
25 https://doi.org/10.1017/cbo9780511804090
26 https://doi.org/10.1080/00927870802243580
27 https://doi.org/10.1090/conm/677/13625
28 https://doi.org/10.1090/s0002-9939-1965-0172274-5
29 https://doi.org/10.1090/s0002-9939-1978-0500555-0
30 https://doi.org/10.1090/s0025-5718-2014-02880-9
31 https://doi.org/10.1109/tit.2005.850116
32 https://doi.org/10.1137/0202025
33 https://doi.org/10.1142/s0218196706003001
34 https://doi.org/10.1142/s0218196706003372
35 https://doi.org/10.1142/s0218196708004548
36 https://doi.org/10.1145/258533.258590
37 https://doi.org/10.1145/321250.321254
38 https://doi.org/10.1145/322077.322083
39 https://doi.org/10.1145/322276.322287
40 https://doi.org/10.1145/322358.322373
41 https://doi.org/10.1307/mmj/1030132408
42 https://doi.org/10.1515/gcc-2012-0016
43 https://doi.org/10.2140/agt.2004.4.439
44 https://doi.org/10.2307/3597196
45 https://doi.org/10.3934/era.2009.16.44
46 schema:datePublished 2018-01
47 schema:datePublishedReg 2018-01-01
48 schema:description It is shown that the knapsack problem, which was introduced by Myasnikov et al. for arbitrary finitely generated groups, can be solved in NP for every graph group. This result even holds if the group elements are represented in a compressed form by so called straight-line programs, which generalizes the classical NP-completeness result of the integer knapsack problem. If group elements are represented explicitly by words over the generators, then knapsack for a graph group belongs to the class LogCFL (a subclass of P) if the graph group can be built up from the trivial group using the operations of free product and direct product with ℤ. In all other cases, the knapsack problem is NP-complete.
49 schema:genre research_article
50 schema:inLanguage en
51 schema:isAccessibleForFree false
52 schema:isPartOf N5bbf6d87ad61433ebe2b5bf168b3c959
53 Nb932c63ecd234ca9a9a9c8bbc1f01120
54 sg:journal.1052098
55 schema:name Knapsack in Graph Groups
56 schema:pagination 192-246
57 schema:productId N40a3d7e069df4ed3a8aa57cb1531351e
58 N9e2a02559f094ff9b9b06a09b27a5b2b
59 Nf8bbf4a1143f40638e511cd453f65500
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091596501
61 https://doi.org/10.1007/s00224-017-9808-3
62 schema:sdDatePublished 2019-04-10T18:32
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher Nb7df693d11de45f18a41e251f14ebd44
65 schema:url http://link.springer.com/10.1007%2Fs00224-017-9808-3
66 sgo:license sg:explorer/license/
67 sgo:sdDataset articles
68 rdf:type schema:ScholarlyArticle
69 N40a3d7e069df4ed3a8aa57cb1531351e schema:name doi
70 schema:value 10.1007/s00224-017-9808-3
71 rdf:type schema:PropertyValue
72 N5bbf6d87ad61433ebe2b5bf168b3c959 schema:issueNumber 1
73 rdf:type schema:PublicationIssue
74 N992a901b13ed4e52a58de9156ad7a865 rdf:first sg:person.015611460437.34
75 rdf:rest Nb93aaa79f0be4cb28079dea89bdb1545
76 N9e2a02559f094ff9b9b06a09b27a5b2b schema:name readcube_id
77 schema:value 396f6cb632f67e4a9bd84bf2258b55d63dace682da63f498d9fdc0c9fc05116e
78 rdf:type schema:PropertyValue
79 Nb7df693d11de45f18a41e251f14ebd44 schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 Nb932c63ecd234ca9a9a9c8bbc1f01120 schema:volumeNumber 62
82 rdf:type schema:PublicationVolume
83 Nb93aaa79f0be4cb28079dea89bdb1545 rdf:first sg:person.014551676263.38
84 rdf:rest rdf:nil
85 Nf8bbf4a1143f40638e511cd453f65500 schema:name dimensions_id
86 schema:value pub.1091596501
87 rdf:type schema:PropertyValue
88 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
89 schema:name Information and Computing Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
92 schema:name Computation Theory and Mathematics
93 rdf:type schema:DefinedTerm
94 sg:journal.1052098 schema:issn 1432-4350
95 1433-0490
96 schema:name Theory of Computing Systems
97 rdf:type schema:Periodical
98 sg:person.014551676263.38 schema:affiliation https://www.grid.ac/institutes/grid.464035.0
99 schema:familyName Zetzsche
100 schema:givenName Georg
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014551676263.38
102 rdf:type schema:Person
103 sg:person.015611460437.34 schema:affiliation https://www.grid.ac/institutes/grid.5836.8
104 schema:familyName Lohrey
105 schema:givenName Markus
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015611460437.34
107 rdf:type schema:Person
108 sg:pub.10.1007/3-540-48340-3_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030203570
109 https://doi.org/10.1007/3-540-48340-3_8
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/3-540-53031-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109702479
112 https://doi.org/10.1007/3-540-53031-2
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/3-540-53904-2_94 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018800611
115 https://doi.org/10.1007/3-540-53904-2_94
116 rdf:type schema:CreativeWork
117 sg:pub.10.1007/978-1-4684-2001-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007977430
118 https://doi.org/10.1007/978-1-4684-2001-2_9
119 rdf:type schema:CreativeWork
120 sg:pub.10.1007/978-1-4939-0748-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017532757
121 https://doi.org/10.1007/978-1-4939-0748-9
122 rdf:type schema:CreativeWork
123 sg:pub.10.1007/978-3-319-21398-9_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018165371
124 https://doi.org/10.1007/978-3-319-21398-9_19
125 rdf:type schema:CreativeWork
126 sg:pub.10.1007/978-3-540-74510-5_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031210348
127 https://doi.org/10.1007/978-3-540-74510-5_26
128 rdf:type schema:CreativeWork
129 sg:pub.10.1007/978-3-662-03927-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010704788
130 https://doi.org/10.1007/978-3-662-03927-4
131 rdf:type schema:CreativeWork
132 sg:pub.10.1007/bf02088289 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020923430
133 https://doi.org/10.1007/bf02088289
134 rdf:type schema:CreativeWork
135 sg:pub.10.1007/s002220050168 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047153124
136 https://doi.org/10.1007/s002220050168
137 rdf:type schema:CreativeWork
138 https://app.dimensions.ai/details/publication/pub.1098909602 schema:CreativeWork
139 https://doi.org/10.1016/0020-0190(95)00017-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026732294
140 rdf:type schema:CreativeWork
141 https://doi.org/10.1016/0890-5401(89)90051-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002448602
142 rdf:type schema:CreativeWork
143 https://doi.org/10.1016/j.aam.2005.08.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032366230
144 rdf:type schema:CreativeWork
145 https://doi.org/10.1016/j.aim.2010.01.011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049624204
146 rdf:type schema:CreativeWork
147 https://doi.org/10.1016/j.ipl.2009.06.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018736955
148 rdf:type schema:CreativeWork
149 https://doi.org/10.1016/j.jalgebra.2007.08.025 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052736790
150 rdf:type schema:CreativeWork
151 https://doi.org/10.1016/j.jsc.2015.05.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000757901
152 rdf:type schema:CreativeWork
153 https://doi.org/10.1016/j.jsc.2015.11.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048617341
154 rdf:type schema:CreativeWork
155 https://doi.org/10.1016/j.jsc.2017.03.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084092369
156 rdf:type schema:CreativeWork
157 https://doi.org/10.1016/s0022-0000(02)00025-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022572190
158 rdf:type schema:CreativeWork
159 https://doi.org/10.1017/cbo9780511804090 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098662846
160 rdf:type schema:CreativeWork
161 https://doi.org/10.1080/00927870802243580 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039759685
162 rdf:type schema:CreativeWork
163 https://doi.org/10.1090/conm/677/13625 schema:sameAs https://app.dimensions.ai/details/publication/pub.1087152886
164 rdf:type schema:CreativeWork
165 https://doi.org/10.1090/s0002-9939-1965-0172274-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027030070
166 rdf:type schema:CreativeWork
167 https://doi.org/10.1090/s0002-9939-1978-0500555-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024056895
168 rdf:type schema:CreativeWork
169 https://doi.org/10.1090/s0025-5718-2014-02880-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031890506
170 rdf:type schema:CreativeWork
171 https://doi.org/10.1109/tit.2005.850116 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061650556
172 rdf:type schema:CreativeWork
173 https://doi.org/10.1137/0202025 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841213
174 rdf:type schema:CreativeWork
175 https://doi.org/10.1142/s0218196706003001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062961263
176 rdf:type schema:CreativeWork
177 https://doi.org/10.1142/s0218196706003372 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062961298
178 rdf:type schema:CreativeWork
179 https://doi.org/10.1142/s0218196708004548 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062961416
180 rdf:type schema:CreativeWork
181 https://doi.org/10.1145/258533.258590 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051965740
182 rdf:type schema:CreativeWork
183 https://doi.org/10.1145/321250.321254 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001877493
184 rdf:type schema:CreativeWork
185 https://doi.org/10.1145/322077.322083 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039489555
186 rdf:type schema:CreativeWork
187 https://doi.org/10.1145/322276.322287 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020447697
188 rdf:type schema:CreativeWork
189 https://doi.org/10.1145/322358.322373 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005188359
190 rdf:type schema:CreativeWork
191 https://doi.org/10.1307/mmj/1030132408 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064976885
192 rdf:type schema:CreativeWork
193 https://doi.org/10.1515/gcc-2012-0016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032881373
194 rdf:type schema:CreativeWork
195 https://doi.org/10.2140/agt.2004.4.439 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069057445
196 rdf:type schema:CreativeWork
197 https://doi.org/10.2307/3597196 schema:sameAs https://app.dimensions.ai/details/publication/pub.1070385308
198 rdf:type schema:CreativeWork
199 https://doi.org/10.3934/era.2009.16.44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1071738731
200 rdf:type schema:CreativeWork
201 https://www.grid.ac/institutes/grid.464035.0 schema:alternateName Laboratoire Spécification et Vérification
202 schema:name LSV, CNRS & ENS Paris-Saclay, Paris, France
203 rdf:type schema:Organization
204 https://www.grid.ac/institutes/grid.5836.8 schema:alternateName University of Siegen
205 schema:name Universität Siegen, Siegen, Germany
206 rdf:type schema:Organization
 




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


...