The Complexity of Compressed Membership Problems for Finite Automata View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2013-01-18

AUTHORS

Artur Jeż

ABSTRACT

In this paper, a compressed membership problem for finite automata, both deterministic (DFAs) and non-deterministic (NFAs), with compressed transition labels is studied. The compression is represented by straight-line programs (SLPs), i.e. context-free grammars generating exactly one string. A novel technique of dealing with SLPs is employed: the SLPs are recompressed, so that substrings of the input word are encoded in SLPs labelling the transitions of the NFA (DFA) in the same way, as in the SLP representing the input text. To this end, the SLPs are locally decompressed and then recompressed in a uniform way. Furthermore, in order to reflect the recompression in the NFA, we need to modify it only a little, in particular its size stays polynomial in the input size.Using this technique it is shown that the compressed membership for NFA with compressed labels is in NP, thus confirming the conjecture of Plandowski and Rytter (Jewels Are Forever, pp. 262–272, Springer, Berlin, 1999) and extending the partial result of Lohrey and Mathissen (in CSR, LNCS, vol. 6651, pp. 275–288, Springer, Berlin, 2011); as this problem is known to be NP-hard (in Plandowski and Rytter, Jewels Are Forever, pp. 262–272, Springer, Berlin, 1999), we settle its exact computational complexity. Moreover, the same technique applied to the compressed membership for DFA with compressed labels yields that this problem is in P, and this problem is known to be P-hard (in Markey and Schnoebelen, Inf. Process. Lett. 90(1):3–6, 2004; Beaudry et al., SIAM J. Comput. 26(1):138–152, 1997). More... »

PAGES

685-718

References to SciGraph publications

  • 1996. Randomized efficient algorithms for compressed strings: the finger-print approach in COMBINATORIAL PATTERN MATCHING
  • 2006. Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2006
  • 2006. Querying and Embedding Compressed Texts in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2006
  • 2012. Faster Fully Compressed Pattern Matching by Recompression in AUTOMATA, LANGUAGES, AND PROGRAMMING
  • 2009-12-23. Complexity of Equations over Sets of Natural Numbers in THEORY OF COMPUTING SYSTEMS
  • 1994. Testing equivalence of morphisms on context-free languages in ALGORITHMS — ESA '94
  • 1997-02. Maintaining dynamic sequences under equality tests in polylogarithmic time in ALGORITHMICA
  • 1995. Pattern matching in compressed texts in FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • 2011-03-10. One-Nonterminal Conjunctive Grammars over a Unary Alphabet in THEORY OF COMPUTING SYSTEMS
  • 2007-01-01. Efficient Computation in Groups Via Compression in COMPUTER SCIENCE – THEORY AND APPLICATIONS
  • 1998. Application of Lempel-Ziv encodings to the solution of word equations in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2011. Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic in ALGORITHMS – ESA 2011
  • 1996. Efficient algorithms for Lempel-Ziv encoding in ALGORITHM THEORY — SWAT'96
  • 2011. Compressed Membership in Automata with Compressed Labels in COMPUTER SCIENCE – THEORY AND APPLICATIONS
  • 2007-10-06. Pattern Matching and Membership for Hierarchical Message Sequence Charts in THEORY OF COMPUTING SYSTEMS
  • 1999. Complexity of Language Recognition Problems for Compressed Words in JEWELS ARE FOREVER
  • 2012. Simple and Efficient LZW-Compressed Multiple Pattern Matching in COMBINATORIAL PATTERN MATCHING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-013-9443-6

    DOI

    http://dx.doi.org/10.1007/s00224-013-9443-6

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie 15, 50-383, Wroc\u0142aw, Poland", 
              "id": "http://www.grid.ac/institutes/grid.8505.8", 
              "name": [
                "Max Planck Institute f\u00fcr Informatik, Campus E1 4, 66123, Saarbr\u00fccken, Germany", 
                "Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie 15, 50-383, Wroc\u0142aw, Poland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Je\u017c", 
            "givenName": "Artur", 
            "id": "sg:person.015252371751.76", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bfb0049431", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036904640", 
              "https://doi.org/10.1007/bfb0049431"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-20712-9_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012277274", 
              "https://doi.org/10.1007/978-3-642-20712-9_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-007-9054-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028694588", 
              "https://doi.org/10.1007/s00224-007-9054-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11821069_56", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016750099", 
              "https://doi.org/10.1007/11821069_56"
            ], 
            "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/3-540-61258-0_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034452299", 
              "https://doi.org/10.1007/3-540-61258-0_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-61422-2_148", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003581531", 
              "https://doi.org/10.1007/3-540-61422-2_148"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-31594-7_45", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026589735", 
              "https://doi.org/10.1007/978-3-642-31594-7_45"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60692-0_60", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035086190", 
              "https://doi.org/10.1007/3-540-60692-0_60"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-23719-5_36", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038685053", 
              "https://doi.org/10.1007/978-3-642-23719-5_36"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02522825", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007699916", 
              "https://doi.org/10.1007/bf02522825"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0055097", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026190890", 
              "https://doi.org/10.1007/bfb0055097"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-60207-8_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050084589", 
              "https://doi.org/10.1007/978-3-642-60207-8_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11821069_59", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020993578", 
              "https://doi.org/10.1007/11821069_59"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-011-9319-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047527460", 
              "https://doi.org/10.1007/s00224-011-9319-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-31265-6_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002667067", 
              "https://doi.org/10.1007/978-3-642-31265-6_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-009-9246-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003872386", 
              "https://doi.org/10.1007/s00224-009-9246-y"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2013-01-18", 
        "datePublishedReg": "2013-01-18", 
        "description": "In this paper, a compressed membership problem for finite automata, both deterministic (DFAs) and non-deterministic (NFAs), with compressed transition labels is studied. The compression is represented by straight-line programs (SLPs), i.e. context-free grammars generating exactly one string. A\u00a0novel technique of dealing with SLPs is employed: the SLPs are recompressed, so that substrings of the input word are encoded in SLPs labelling the transitions of the NFA (DFA) in the same way, as in the SLP representing the input text. To this end, the SLPs are locally decompressed and then recompressed in a uniform way. Furthermore, in order to reflect the recompression in the NFA, we need to modify it only a little, in particular its size stays polynomial in the input size.Using this technique it is shown that the compressed membership for NFA with compressed labels is in NP, thus confirming the conjecture of Plandowski and Rytter (Jewels Are Forever, pp. 262\u2013272, Springer, Berlin, 1999) and extending the partial result of Lohrey and Mathissen (in CSR, LNCS, vol. 6651, pp.\u00a0275\u2013288, Springer, Berlin, 2011); as this problem is known to be NP-hard (in Plandowski and Rytter, Jewels Are Forever, pp.\u00a0262\u2013272, Springer, Berlin, 1999), we settle its exact computational complexity. Moreover, the same technique applied to the compressed membership for DFA with compressed labels yields that this problem is in P, and this problem is known to be P-hard (in Markey and Schnoebelen, Inf. Process. Lett. 90(1):3\u20136, 2004; Beaudry et\u00a0al., SIAM J. Comput. 26(1):138\u2013152, 1997).", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00224-013-9443-6", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "55"
          }
        ], 
        "keywords": [
          "straight-line programs", 
          "exact computational complexity", 
          "finite automata", 
          "context-free grammars", 
          "input text", 
          "computational complexity", 
          "input size", 
          "membership problem", 
          "uniform way", 
          "input word", 
          "transition labels", 
          "automata", 
          "partial results", 
          "complexity", 
          "novel technique", 
          "NPs", 
          "labels", 
          "NFA", 
          "substrings", 
          "Lohrey", 
          "technique", 
          "Plandowski", 
          "Rytter", 
          "way", 
          "text", 
          "grammar", 
          "compression", 
          "strings", 
          "same way", 
          "recompression", 
          "words", 
          "same technique", 
          "DFA", 
          "membership", 
          "order", 
          "program", 
          "end", 
          "size", 
          "results", 
          "conjecture", 
          "transition", 
          "yield", 
          "problem", 
          "paper"
        ], 
        "name": "The Complexity of Compressed Membership Problems for Finite Automata", 
        "pagination": "685-718", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1049189041"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-013-9443-6"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-013-9443-6", 
          "https://app.dimensions.ai/details/publication/pub.1049189041"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-10T10:06", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_606.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00224-013-9443-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-013-9443-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-013-9443-6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-013-9443-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-013-9443-6'


     

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

    171 TRIPLES      22 PREDICATES      86 URIs      61 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-013-9443-6 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N010abe49af664282bd84cce8079b85bc
    4 schema:citation sg:pub.10.1007/11821069_56
    5 sg:pub.10.1007/11821069_59
    6 sg:pub.10.1007/3-540-60692-0_60
    7 sg:pub.10.1007/3-540-61258-0_3
    8 sg:pub.10.1007/3-540-61422-2_148
    9 sg:pub.10.1007/978-3-540-74510-5_26
    10 sg:pub.10.1007/978-3-642-20712-9_21
    11 sg:pub.10.1007/978-3-642-23719-5_36
    12 sg:pub.10.1007/978-3-642-31265-6_19
    13 sg:pub.10.1007/978-3-642-31594-7_45
    14 sg:pub.10.1007/978-3-642-60207-8_23
    15 sg:pub.10.1007/bf02522825
    16 sg:pub.10.1007/bfb0049431
    17 sg:pub.10.1007/bfb0055097
    18 sg:pub.10.1007/s00224-007-9054-1
    19 sg:pub.10.1007/s00224-009-9246-y
    20 sg:pub.10.1007/s00224-011-9319-6
    21 schema:datePublished 2013-01-18
    22 schema:datePublishedReg 2013-01-18
    23 schema:description In this paper, a compressed membership problem for finite automata, both deterministic (DFAs) and non-deterministic (NFAs), with compressed transition labels is studied. The compression is represented by straight-line programs (SLPs), i.e. context-free grammars generating exactly one string. A novel technique of dealing with SLPs is employed: the SLPs are recompressed, so that substrings of the input word are encoded in SLPs labelling the transitions of the NFA (DFA) in the same way, as in the SLP representing the input text. To this end, the SLPs are locally decompressed and then recompressed in a uniform way. Furthermore, in order to reflect the recompression in the NFA, we need to modify it only a little, in particular its size stays polynomial in the input size.Using this technique it is shown that the compressed membership for NFA with compressed labels is in NP, thus confirming the conjecture of Plandowski and Rytter (Jewels Are Forever, pp. 262–272, Springer, Berlin, 1999) and extending the partial result of Lohrey and Mathissen (in CSR, LNCS, vol. 6651, pp. 275–288, Springer, Berlin, 2011); as this problem is known to be NP-hard (in Plandowski and Rytter, Jewels Are Forever, pp. 262–272, Springer, Berlin, 1999), we settle its exact computational complexity. Moreover, the same technique applied to the compressed membership for DFA with compressed labels yields that this problem is in P, and this problem is known to be P-hard (in Markey and Schnoebelen, Inf. Process. Lett. 90(1):3–6, 2004; Beaudry et al., SIAM J. Comput. 26(1):138–152, 1997).
    24 schema:genre article
    25 schema:inLanguage en
    26 schema:isAccessibleForFree true
    27 schema:isPartOf N15998e0e3e724ae5a53e0cca96eadf36
    28 Nb16180a9b87c41b8911a1042574e6dcb
    29 sg:journal.1052098
    30 schema:keywords DFA
    31 Lohrey
    32 NFA
    33 NPs
    34 Plandowski
    35 Rytter
    36 automata
    37 complexity
    38 compression
    39 computational complexity
    40 conjecture
    41 context-free grammars
    42 end
    43 exact computational complexity
    44 finite automata
    45 grammar
    46 input size
    47 input text
    48 input word
    49 labels
    50 membership
    51 membership problem
    52 novel technique
    53 order
    54 paper
    55 partial results
    56 problem
    57 program
    58 recompression
    59 results
    60 same technique
    61 same way
    62 size
    63 straight-line programs
    64 strings
    65 substrings
    66 technique
    67 text
    68 transition
    69 transition labels
    70 uniform way
    71 way
    72 words
    73 yield
    74 schema:name The Complexity of Compressed Membership Problems for Finite Automata
    75 schema:pagination 685-718
    76 schema:productId N57675042531f4a9e9a381edeb0852f00
    77 Nad12d47ac3ae4db2b0502a2654bed20a
    78 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049189041
    79 https://doi.org/10.1007/s00224-013-9443-6
    80 schema:sdDatePublished 2022-05-10T10:06
    81 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    82 schema:sdPublisher N3720950747fa4b29a64cfa5b392c817e
    83 schema:url https://doi.org/10.1007/s00224-013-9443-6
    84 sgo:license sg:explorer/license/
    85 sgo:sdDataset articles
    86 rdf:type schema:ScholarlyArticle
    87 N010abe49af664282bd84cce8079b85bc rdf:first sg:person.015252371751.76
    88 rdf:rest rdf:nil
    89 N15998e0e3e724ae5a53e0cca96eadf36 schema:volumeNumber 55
    90 rdf:type schema:PublicationVolume
    91 N3720950747fa4b29a64cfa5b392c817e schema:name Springer Nature - SN SciGraph project
    92 rdf:type schema:Organization
    93 N57675042531f4a9e9a381edeb0852f00 schema:name doi
    94 schema:value 10.1007/s00224-013-9443-6
    95 rdf:type schema:PropertyValue
    96 Nad12d47ac3ae4db2b0502a2654bed20a schema:name dimensions_id
    97 schema:value pub.1049189041
    98 rdf:type schema:PropertyValue
    99 Nb16180a9b87c41b8911a1042574e6dcb schema:issueNumber 4
    100 rdf:type schema:PublicationIssue
    101 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    102 schema:name Information and Computing Sciences
    103 rdf:type schema:DefinedTerm
    104 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    105 schema:name Computation Theory and Mathematics
    106 rdf:type schema:DefinedTerm
    107 sg:journal.1052098 schema:issn 1432-4350
    108 1433-0490
    109 schema:name Theory of Computing Systems
    110 schema:publisher Springer Nature
    111 rdf:type schema:Periodical
    112 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
    113 schema:familyName Jeż
    114 schema:givenName Artur
    115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
    116 rdf:type schema:Person
    117 sg:pub.10.1007/11821069_56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016750099
    118 https://doi.org/10.1007/11821069_56
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/11821069_59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020993578
    121 https://doi.org/10.1007/11821069_59
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/3-540-60692-0_60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035086190
    124 https://doi.org/10.1007/3-540-60692-0_60
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/3-540-61258-0_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034452299
    127 https://doi.org/10.1007/3-540-61258-0_3
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/3-540-61422-2_148 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003581531
    130 https://doi.org/10.1007/3-540-61422-2_148
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/978-3-540-74510-5_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031210348
    133 https://doi.org/10.1007/978-3-540-74510-5_26
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/978-3-642-20712-9_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012277274
    136 https://doi.org/10.1007/978-3-642-20712-9_21
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/978-3-642-23719-5_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038685053
    139 https://doi.org/10.1007/978-3-642-23719-5_36
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/978-3-642-31265-6_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002667067
    142 https://doi.org/10.1007/978-3-642-31265-6_19
    143 rdf:type schema:CreativeWork
    144 sg:pub.10.1007/978-3-642-31594-7_45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026589735
    145 https://doi.org/10.1007/978-3-642-31594-7_45
    146 rdf:type schema:CreativeWork
    147 sg:pub.10.1007/978-3-642-60207-8_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050084589
    148 https://doi.org/10.1007/978-3-642-60207-8_23
    149 rdf:type schema:CreativeWork
    150 sg:pub.10.1007/bf02522825 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007699916
    151 https://doi.org/10.1007/bf02522825
    152 rdf:type schema:CreativeWork
    153 sg:pub.10.1007/bfb0049431 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036904640
    154 https://doi.org/10.1007/bfb0049431
    155 rdf:type schema:CreativeWork
    156 sg:pub.10.1007/bfb0055097 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026190890
    157 https://doi.org/10.1007/bfb0055097
    158 rdf:type schema:CreativeWork
    159 sg:pub.10.1007/s00224-007-9054-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028694588
    160 https://doi.org/10.1007/s00224-007-9054-1
    161 rdf:type schema:CreativeWork
    162 sg:pub.10.1007/s00224-009-9246-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1003872386
    163 https://doi.org/10.1007/s00224-009-9246-y
    164 rdf:type schema:CreativeWork
    165 sg:pub.10.1007/s00224-011-9319-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047527460
    166 https://doi.org/10.1007/s00224-011-9319-6
    167 rdf:type schema:CreativeWork
    168 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50-383, Wrocław, Poland
    169 schema:name Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50-383, Wrocław, Poland
    170 Max Planck Institute für Informatik, Campus E1 4, 66123, Saarbrücken, Germany
    171 rdf:type schema:Organization
     




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


    ...