On the complexity of pattern matching for highly compressed two-dimensional texts View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1997

AUTHORS

Piotr Berman , Marek Karpinski , Lawrence L. Larmore , Wojciech Plandowski , Wojciech Rytter

ABSTRACT

We consider the complexity of problems related to 2-dimensional texts (2d-texts) described succinctly. In a succinct description, larger rectangular sub-texts are defined in terms of smaller parts in a way similar to that of Lempel-Ziv compression for 1-dimensional texts, or in shortly described strings as in [9], or in hierarchical graphs described by context-free graph grammars. A given 2d-text T with many internal repetitions can have a hierarchical description (denoted Compress(T)) which is up to exponentially smaller and which can be the only part of the input for a pattern-matching algorithm which gives information about T. Such a hierarchical description is given in terms of a straight-line program, see [9] or, equivalently, a 2-dimensional grammar.We consider compressed pattern-matching, where the input consists of a 2d-pattern P and of a hierarchical description of a 2d-text T, and fully compressed pattern-matching, where the input consists of hierarchical descriptions of both the pattern P and the text T. For 1-dimensional strings there exist polynomial-time deterministic algorithms for these problems, for similar types of succinct text descriptions [2, 6, 8, 9]. We show that the complexity dramatically increases in a 2-dimensional setting. For example, compressed 2d-matching is NP-complete, fully compressed 2d-matching is Σ2p-complete, and testing a given occurrence of a two dimensional compressed pattern is co-NP-complete.On the other hand, we give efficient algorithms for the related problems of randomized equality testing and testing for a given occurrence of an uncompressed pattern.We also show the surprising fact that the compressed size of a subrectangle of a compressed 2d-text can grow exponentially, unlike the one dimensional case. More... »

PAGES

40-51

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-63220-4_48

DOI

http://dx.doi.org/10.1007/3-540-63220-4_48

DIMENSIONS

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


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": "Dept. of Computer Science & Eng., Pensylvania State University, PA16802, University Park, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Dept. of Computer Science & Eng., Pensylvania State University, PA16802, University Park, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, D-53117, Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, D-53117, Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Nevada, 89154-4019, Las Vegas, NV", 
          "id": "http://www.grid.ac/institutes/grid.272362.0", 
          "name": [
            "Department of Computer Science, University of Nevada, 89154-4019, Las Vegas, NV"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Larmore", 
        "givenName": "Lawrence L.", 
        "id": "sg:person.01045732472.72", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01045732472.72"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warsaw", 
          "id": "http://www.grid.ac/institutes/grid.12847.38", 
          "name": [
            "Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warsaw"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Plandowski", 
        "givenName": "Wojciech", 
        "id": "sg:person.010207617143.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010207617143.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Liverpool, UK", 
          "id": "http://www.grid.ac/institutes/grid.10025.36", 
          "name": [
            "Department of Computer Science, University of Liverpool, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rytter", 
        "givenName": "Wojciech", 
        "id": "sg:person.013534566577.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013534566577.61"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1997", 
    "datePublishedReg": "1997-01-01", 
    "description": "We consider the complexity of problems related to 2-dimensional texts (2d-texts) described succinctly. In a succinct description, larger rectangular sub-texts are defined in terms of smaller parts in a way similar to that of Lempel-Ziv compression for 1-dimensional texts, or in shortly described strings as in [9], or in hierarchical graphs described by context-free graph grammars. A given 2d-text T with many internal repetitions can have a hierarchical description (denoted Compress(T)) which is up to exponentially smaller and which can be the only part of the input for a pattern-matching algorithm which gives information about T. Such a hierarchical description is given in terms of a straight-line program, see [9] or, equivalently, a 2-dimensional grammar.We consider compressed pattern-matching, where the input consists of a 2d-pattern P and of a hierarchical description of a 2d-text T, and fully compressed pattern-matching, where the input consists of hierarchical descriptions of both the pattern P and the text T. For 1-dimensional strings there exist polynomial-time deterministic algorithms for these problems, for similar types of succinct text descriptions [2, 6, 8, 9]. We show that the complexity dramatically increases in a 2-dimensional setting. For example, compressed 2d-matching is NP-complete, fully compressed 2d-matching is \u03a32p-complete, and testing a given occurrence of a two dimensional compressed pattern is co-NP-complete.On the other hand, we give efficient algorithms for the related problems of randomized equality testing and testing for a given occurrence of an uncompressed pattern.We also show the surprising fact that the compressed size of a subrectangle of a compressed 2d-text can grow exponentially, unlike the one dimensional case.", 
    "editor": [
      {
        "familyName": "Apostolico", 
        "givenName": "Alberto", 
        "type": "Person"
      }, 
      {
        "familyName": "Hein", 
        "givenName": "Jotun", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-63220-4_48", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-63220-7", 
        "978-3-540-69214-0"
      ], 
      "name": "Combinatorial Pattern Matching", 
      "type": "Book"
    }, 
    "keywords": [
      "hierarchical description", 
      "polynomial-time deterministic algorithm", 
      "Lempel-Ziv compression", 
      "pattern matching algorithm", 
      "two-dimensional text", 
      "context-free graph grammars", 
      "complexity of problems", 
      "uncompressed pattern", 
      "hierarchical graph", 
      "equality testing", 
      "text descriptions", 
      "straight-line programs", 
      "text T.", 
      "graph grammars", 
      "efficient algorithm", 
      "pattern P", 
      "deterministic algorithm", 
      "complexity of patterns", 
      "algorithm", 
      "complexity", 
      "related problems", 
      "succinct description", 
      "text", 
      "input", 
      "grammar", 
      "graph", 
      "subrectangles", 
      "string", 
      "small part", 
      "NPs", 
      "only part", 
      "description", 
      "information", 
      "compression", 
      "similar types", 
      "terms", 
      "way", 
      "example", 
      "testing", 
      "surprising fact", 
      "part", 
      "internal repetition", 
      "patterns", 
      "hand", 
      "program", 
      "dimensional case", 
      "fact", 
      "setting", 
      "types", 
      "repetition", 
      "size", 
      "cases", 
      "T.", 
      "occurrence", 
      "problem"
    ], 
    "name": "On the complexity of pattern matching for highly compressed two-dimensional texts", 
    "pagination": "40-51", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1032715182"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-63220-4_48"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-63220-4_48", 
      "https://app.dimensions.ai/details/publication/pub.1032715182"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:18", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_280.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-63220-4_48"
  }
]
 

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/3-540-63220-4_48'

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/3-540-63220-4_48'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-63220-4_48'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-63220-4_48'


 

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

159 TRIPLES      22 PREDICATES      80 URIs      73 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-63220-4_48 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N11b4513a076e4c8d9f6652f0eb99c48a
4 schema:datePublished 1997
5 schema:datePublishedReg 1997-01-01
6 schema:description We consider the complexity of problems related to 2-dimensional texts (2d-texts) described succinctly. In a succinct description, larger rectangular sub-texts are defined in terms of smaller parts in a way similar to that of Lempel-Ziv compression for 1-dimensional texts, or in shortly described strings as in [9], or in hierarchical graphs described by context-free graph grammars. A given 2d-text T with many internal repetitions can have a hierarchical description (denoted Compress(T)) which is up to exponentially smaller and which can be the only part of the input for a pattern-matching algorithm which gives information about T. Such a hierarchical description is given in terms of a straight-line program, see [9] or, equivalently, a 2-dimensional grammar.We consider compressed pattern-matching, where the input consists of a 2d-pattern P and of a hierarchical description of a 2d-text T, and fully compressed pattern-matching, where the input consists of hierarchical descriptions of both the pattern P and the text T. For 1-dimensional strings there exist polynomial-time deterministic algorithms for these problems, for similar types of succinct text descriptions [2, 6, 8, 9]. We show that the complexity dramatically increases in a 2-dimensional setting. For example, compressed 2d-matching is NP-complete, fully compressed 2d-matching is Σ2p-complete, and testing a given occurrence of a two dimensional compressed pattern is co-NP-complete.On the other hand, we give efficient algorithms for the related problems of randomized equality testing and testing for a given occurrence of an uncompressed pattern.We also show the surprising fact that the compressed size of a subrectangle of a compressed 2d-text can grow exponentially, unlike the one dimensional case.
7 schema:editor Ne9830a74aa80417bb9e1e7351df10c51
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nd2e1a8fef98840c0b317162704a514e1
11 schema:keywords Lempel-Ziv compression
12 NPs
13 T.
14 algorithm
15 cases
16 complexity
17 complexity of patterns
18 complexity of problems
19 compression
20 context-free graph grammars
21 description
22 deterministic algorithm
23 dimensional case
24 efficient algorithm
25 equality testing
26 example
27 fact
28 grammar
29 graph
30 graph grammars
31 hand
32 hierarchical description
33 hierarchical graph
34 information
35 input
36 internal repetition
37 occurrence
38 only part
39 part
40 pattern P
41 pattern matching algorithm
42 patterns
43 polynomial-time deterministic algorithm
44 problem
45 program
46 related problems
47 repetition
48 setting
49 similar types
50 size
51 small part
52 straight-line programs
53 string
54 subrectangles
55 succinct description
56 surprising fact
57 terms
58 testing
59 text
60 text T.
61 text descriptions
62 two-dimensional text
63 types
64 uncompressed pattern
65 way
66 schema:name On the complexity of pattern matching for highly compressed two-dimensional texts
67 schema:pagination 40-51
68 schema:productId N3a584cc831a04cf1b04460d2009797e1
69 N620f83a1ee82457c8ee76721ea450f5b
70 schema:publisher Nbd930323781149278b0a9e42ec3914c9
71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032715182
72 https://doi.org/10.1007/3-540-63220-4_48
73 schema:sdDatePublished 2022-08-04T17:18
74 schema:sdLicense https://scigraph.springernature.com/explorer/license/
75 schema:sdPublisher Nf85daa83fa8d48e79cb8b448e2502250
76 schema:url https://doi.org/10.1007/3-540-63220-4_48
77 sgo:license sg:explorer/license/
78 sgo:sdDataset chapters
79 rdf:type schema:Chapter
80 N11b4513a076e4c8d9f6652f0eb99c48a rdf:first sg:person.01274506210.27
81 rdf:rest Nd73360b05c6b46f5938287135e6f9c4f
82 N3a584cc831a04cf1b04460d2009797e1 schema:name dimensions_id
83 schema:value pub.1032715182
84 rdf:type schema:PropertyValue
85 N4047ce37f1eb4227aea5c0ffa40ab364 schema:familyName Apostolico
86 schema:givenName Alberto
87 rdf:type schema:Person
88 N52f0d391e3144469be88b848d1967aeb rdf:first sg:person.010207617143.19
89 rdf:rest Na9099e0367d24b88ab5f90bd99efcfb8
90 N620f83a1ee82457c8ee76721ea450f5b schema:name doi
91 schema:value 10.1007/3-540-63220-4_48
92 rdf:type schema:PropertyValue
93 N68997012def34a4e9c835b1a5a506343 rdf:first sg:person.01045732472.72
94 rdf:rest N52f0d391e3144469be88b848d1967aeb
95 N813f50b19424437884c6a3f4b3133930 rdf:first N99f2c3aa823448e0adb72e6488169e68
96 rdf:rest rdf:nil
97 N99f2c3aa823448e0adb72e6488169e68 schema:familyName Hein
98 schema:givenName Jotun
99 rdf:type schema:Person
100 Na9099e0367d24b88ab5f90bd99efcfb8 rdf:first sg:person.013534566577.61
101 rdf:rest rdf:nil
102 Nbd930323781149278b0a9e42ec3914c9 schema:name Springer Nature
103 rdf:type schema:Organisation
104 Nd2e1a8fef98840c0b317162704a514e1 schema:isbn 978-3-540-63220-7
105 978-3-540-69214-0
106 schema:name Combinatorial Pattern Matching
107 rdf:type schema:Book
108 Nd73360b05c6b46f5938287135e6f9c4f rdf:first sg:person.011636042271.02
109 rdf:rest N68997012def34a4e9c835b1a5a506343
110 Ne9830a74aa80417bb9e1e7351df10c51 rdf:first N4047ce37f1eb4227aea5c0ffa40ab364
111 rdf:rest N813f50b19424437884c6a3f4b3133930
112 Nf85daa83fa8d48e79cb8b448e2502250 schema:name Springer Nature - SN SciGraph project
113 rdf:type schema:Organization
114 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
115 schema:name Information and Computing Sciences
116 rdf:type schema:DefinedTerm
117 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
118 schema:name Computation Theory and Mathematics
119 rdf:type schema:DefinedTerm
120 sg:person.010207617143.19 schema:affiliation grid-institutes:grid.12847.38
121 schema:familyName Plandowski
122 schema:givenName Wojciech
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010207617143.19
124 rdf:type schema:Person
125 sg:person.01045732472.72 schema:affiliation grid-institutes:grid.272362.0
126 schema:familyName Larmore
127 schema:givenName Lawrence L.
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01045732472.72
129 rdf:type schema:Person
130 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
131 schema:familyName Karpinski
132 schema:givenName Marek
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
134 rdf:type schema:Person
135 sg:person.01274506210.27 schema:affiliation grid-institutes:None
136 schema:familyName Berman
137 schema:givenName Piotr
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
139 rdf:type schema:Person
140 sg:person.013534566577.61 schema:affiliation grid-institutes:grid.10025.36
141 schema:familyName Rytter
142 schema:givenName Wojciech
143 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013534566577.61
144 rdf:type schema:Person
145 grid-institutes:None schema:alternateName Dept. of Computer Science & Eng., Pensylvania State University, PA16802, University Park, USA
146 schema:name Dept. of Computer Science & Eng., Pensylvania State University, PA16802, University Park, USA
147 rdf:type schema:Organization
148 grid-institutes:grid.10025.36 schema:alternateName Department of Computer Science, University of Liverpool, UK
149 schema:name Department of Computer Science, University of Liverpool, UK
150 rdf:type schema:Organization
151 grid-institutes:grid.10388.32 schema:alternateName Dept. of Computer Science, University of Bonn, D-53117, Bonn, Germany
152 schema:name Dept. of Computer Science, University of Bonn, D-53117, Bonn, Germany
153 rdf:type schema:Organization
154 grid-institutes:grid.12847.38 schema:alternateName Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warsaw
155 schema:name Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warsaw
156 rdf:type schema:Organization
157 grid-institutes:grid.272362.0 schema:alternateName Department of Computer Science, University of Nevada, 89154-4019, Las Vegas, NV
158 schema:name Department of Computer Science, University of Nevada, 89154-4019, Las Vegas, NV
159 rdf:type schema:Organization
 




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


...