Complexity of Language Recognition Problems for Compressed Words View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1999

AUTHORS

Wojciech Plandowski , Wojciech Rytter

ABSTRACT

The compressed recognition problem consists in checking if an input word w is in a given language L, when we are only given a compressed representation of w. We present several new results related to language recognition problems for compressed texts. These problems are solvable in polynomial time for uncompressed words and some of them become NP-hard for compressed words.Two types of compression are considered: Lempel-Ziv compress and compression in terms of straight-line programs (or sequences of recurrencem, or context-free grammars generating single texts). These compreassions are polynomically related and most of our results apply to both of them.Denote by LZ(w) (SLP(w)) the version of a string w produced by Lempel-Ziv encoding (straight-line program). The complexity of the following problem is considered:given a compressed version (LZ(w) or SLP(w)) of the input word w, test the membership w ∈ L, where L is a formal language.The complexity depends on the type and description of the language L. Surprisingly the proofs of NP-hardness are in this area usually easier than the proof that a problem in NP.The membership problem is in DSPACE(n2) for general context-free sets L and in NSPACE(n) for linear languages. We show that for unary languages compressed recognition of context-free languages is NP-complete.We also briefly discuss some known results related to the membership problem for the string-matching languages and for languages related to string-matching: square-free wordsm, squares, palindromes, and primitive words. More... »

PAGES

262-272

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-60207-8_23

DOI

http://dx.doi.org/10.1007/978-3-642-60207-8_23

DIMENSIONS

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


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/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "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"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2004", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Linguistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warszawa, Poland", 
          "id": "http://www.grid.ac/institutes/grid.12847.38", 
          "name": [
            "Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warszawa, Poland"
          ], 
          "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": [
            "Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warszawa, Poland", 
            "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": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "The compressed recognition problem consists in checking if an input word w is in a given language L, when we are only given a compressed representation of w. We present several new results related to language recognition problems for compressed texts. These problems are solvable in polynomial time for uncompressed words and some of them become NP-hard for compressed words.Two types of compression are considered: Lempel-Ziv compress and compression in terms of straight-line programs (or sequences of recurrencem, or context-free grammars generating single texts). These compreassions are polynomically related and most of our results apply to both of them.Denote by LZ(w) (SLP(w)) the version of a string w produced by Lempel-Ziv encoding (straight-line program). The complexity of the following problem is considered:given a compressed version (LZ(w) or SLP(w)) of the input word w, test the membership w \u2208 L, where L is a formal language.The complexity depends on the type and description of the language L. Surprisingly the proofs of NP-hardness are in this area usually easier than the proof that a problem in NP.The membership problem is in DSPACE(n2) for general context-free sets L and in NSPACE(n) for linear languages. We show that for unary languages compressed recognition of context-free languages is NP-complete.We also briefly discuss some known results related to the membership problem for the string-matching languages and for languages related to string-matching: square-free wordsm, squares, palindromes, and primitive words.", 
    "editor": [
      {
        "familyName": "Karhum\u00e4ki", 
        "givenName": "Juhani", 
        "type": "Person"
      }, 
      {
        "familyName": "Maurer", 
        "givenName": "Hermann", 
        "type": "Person"
      }, 
      {
        "familyName": "P\u0103un", 
        "givenName": "Gheorghe", 
        "type": "Person"
      }, 
      {
        "familyName": "Rozenberg", 
        "givenName": "Grzegorz", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-60207-8_23", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-64304-0", 
        "978-3-642-60207-8"
      ], 
      "name": "Jewels are Forever", 
      "type": "Book"
    }, 
    "keywords": [
      "language recognition problem", 
      "recognition problem", 
      "context-free languages", 
      "word w", 
      "straight-line programs", 
      "Lempel-Ziv", 
      "NP-hardness", 
      "formal language", 
      "membership problem", 
      "polynomial time", 
      "language L", 
      "unary languages", 
      "linear languages", 
      "type of compression", 
      "primitive words", 
      "language", 
      "words", 
      "complexity", 
      "NPs", 
      "sets L", 
      "string w", 
      "text", 
      "proof", 
      "compression", 
      "version", 
      "recognition", 
      "representation", 
      "compress", 
      "results", 
      "description", 
      "terms", 
      "program", 
      "time", 
      "types", 
      "new results", 
      "squares", 
      "palindrome", 
      "problem", 
      "area", 
      "Surprisingly"
    ], 
    "name": "Complexity of Language Recognition Problems for Compressed Words", 
    "pagination": "262-272", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050084589"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-60207-8_23"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-60207-8_23", 
      "https://app.dimensions.ai/details/publication/pub.1050084589"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:32", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_303.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-60207-8_23"
  }
]
 

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/978-3-642-60207-8_23'

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/978-3-642-60207-8_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-60207-8_23'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-60207-8_23'


 

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

138 TRIPLES      23 PREDICATES      69 URIs      59 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-60207-8_23 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 anzsrc-for:0802
4 anzsrc-for:20
5 anzsrc-for:2004
6 schema:author N7893755b630c4cd98836de633efa0893
7 schema:datePublished 1999
8 schema:datePublishedReg 1999-01-01
9 schema:description The compressed recognition problem consists in checking if an input word w is in a given language L, when we are only given a compressed representation of w. We present several new results related to language recognition problems for compressed texts. These problems are solvable in polynomial time for uncompressed words and some of them become NP-hard for compressed words.Two types of compression are considered: Lempel-Ziv compress and compression in terms of straight-line programs (or sequences of recurrencem, or context-free grammars generating single texts). These compreassions are polynomically related and most of our results apply to both of them.Denote by LZ(w) (SLP(w)) the version of a string w produced by Lempel-Ziv encoding (straight-line program). The complexity of the following problem is considered:given a compressed version (LZ(w) or SLP(w)) of the input word w, test the membership w ∈ L, where L is a formal language.The complexity depends on the type and description of the language L. Surprisingly the proofs of NP-hardness are in this area usually easier than the proof that a problem in NP.The membership problem is in DSPACE(n2) for general context-free sets L and in NSPACE(n) for linear languages. We show that for unary languages compressed recognition of context-free languages is NP-complete.We also briefly discuss some known results related to the membership problem for the string-matching languages and for languages related to string-matching: square-free wordsm, squares, palindromes, and primitive words.
10 schema:editor Nf9bdc28ff1ef415b89cfa439a1652e59
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N211983a8fd4f452baf8e1b2752ccf044
15 schema:keywords Lempel-Ziv
16 NP-hardness
17 NPs
18 Surprisingly
19 area
20 complexity
21 compress
22 compression
23 context-free languages
24 description
25 formal language
26 language
27 language L
28 language recognition problem
29 linear languages
30 membership problem
31 new results
32 palindrome
33 polynomial time
34 primitive words
35 problem
36 program
37 proof
38 recognition
39 recognition problem
40 representation
41 results
42 sets L
43 squares
44 straight-line programs
45 string w
46 terms
47 text
48 time
49 type of compression
50 types
51 unary languages
52 version
53 word w
54 words
55 schema:name Complexity of Language Recognition Problems for Compressed Words
56 schema:pagination 262-272
57 schema:productId N79e2e6c8a52547eb95d86cb668cabf91
58 Nb41ee0402b754046bd3b29adaaf80183
59 schema:publisher Ndfd549f62b144d899c353ea599e9515e
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050084589
61 https://doi.org/10.1007/978-3-642-60207-8_23
62 schema:sdDatePublished 2022-06-01T22:32
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N158a6f7c8e6b435baed79ebd8e95bcff
65 schema:url https://doi.org/10.1007/978-3-642-60207-8_23
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N158a6f7c8e6b435baed79ebd8e95bcff schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 N211983a8fd4f452baf8e1b2752ccf044 schema:isbn 978-3-642-60207-8
72 978-3-642-64304-0
73 schema:name Jewels are Forever
74 rdf:type schema:Book
75 N4a021a9f87ac46338c654d8c8e04de38 rdf:first N5f17b011bf5748c1a11a0904d922f828
76 rdf:rest Nd3f0a4aa30324874867d5a56abc6fe7b
77 N4fe17eb808804a7d9467c3860ac3c7cb rdf:first Nbd2e6dc54f3744d4907c75ca51651e12
78 rdf:rest rdf:nil
79 N5a784a9ef62c4912ac4d29192a0d054b schema:familyName Karhumäki
80 schema:givenName Juhani
81 rdf:type schema:Person
82 N5f17b011bf5748c1a11a0904d922f828 schema:familyName Maurer
83 schema:givenName Hermann
84 rdf:type schema:Person
85 N7893755b630c4cd98836de633efa0893 rdf:first sg:person.010207617143.19
86 rdf:rest Nd4307a29eb534dfebf6e8713e3d68a4d
87 N79e2e6c8a52547eb95d86cb668cabf91 schema:name doi
88 schema:value 10.1007/978-3-642-60207-8_23
89 rdf:type schema:PropertyValue
90 Nab76252872ba4593810a1809b9ad724a schema:familyName Păun
91 schema:givenName Gheorghe
92 rdf:type schema:Person
93 Nb41ee0402b754046bd3b29adaaf80183 schema:name dimensions_id
94 schema:value pub.1050084589
95 rdf:type schema:PropertyValue
96 Nbd2e6dc54f3744d4907c75ca51651e12 schema:familyName Rozenberg
97 schema:givenName Grzegorz
98 rdf:type schema:Person
99 Nd3f0a4aa30324874867d5a56abc6fe7b rdf:first Nab76252872ba4593810a1809b9ad724a
100 rdf:rest N4fe17eb808804a7d9467c3860ac3c7cb
101 Nd4307a29eb534dfebf6e8713e3d68a4d rdf:first sg:person.013534566577.61
102 rdf:rest rdf:nil
103 Ndfd549f62b144d899c353ea599e9515e schema:name Springer Nature
104 rdf:type schema:Organisation
105 Nf9bdc28ff1ef415b89cfa439a1652e59 rdf:first N5a784a9ef62c4912ac4d29192a0d054b
106 rdf:rest N4a021a9f87ac46338c654d8c8e04de38
107 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
108 schema:name Information and Computing Sciences
109 rdf:type schema:DefinedTerm
110 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
111 schema:name Artificial Intelligence and Image Processing
112 rdf:type schema:DefinedTerm
113 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
114 schema:name Computation Theory and Mathematics
115 rdf:type schema:DefinedTerm
116 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
117 schema:name Language, Communication and Culture
118 rdf:type schema:DefinedTerm
119 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
120 schema:name Linguistics
121 rdf:type schema:DefinedTerm
122 sg:person.010207617143.19 schema:affiliation grid-institutes:grid.12847.38
123 schema:familyName Plandowski
124 schema:givenName Wojciech
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010207617143.19
126 rdf:type schema:Person
127 sg:person.013534566577.61 schema:affiliation grid-institutes:grid.10025.36
128 schema:familyName Rytter
129 schema:givenName Wojciech
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013534566577.61
131 rdf:type schema:Person
132 grid-institutes:grid.10025.36 schema:alternateName Department of Computer Science, University of Liverpool, UK
133 schema:name Department of Computer Science, University of Liverpool, UK
134 Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warszawa, Poland
135 rdf:type schema:Organization
136 grid-institutes:grid.12847.38 schema:alternateName Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warszawa, Poland
137 schema:name Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warszawa, Poland
138 rdf:type schema:Organization
 




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


...