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 Nf7c6fc2aa69d4a83a39be1113f3e3993
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 N07391c280f974945a49bf7626d821398
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf Na108d72b214646f59da7ef0377205950
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 N7155f43e98324b2497138b7f19688959
58 Na1d779c10b174c81a9e656a942a96d11
59 schema:publisher N0f86c3a1d92b4ca3a513278727041d0e
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 Nbe4a1d2572f84d71a318addb6ad50d80
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 N07391c280f974945a49bf7626d821398 rdf:first Nfe38c467034140b9ad0d5f804989b645
70 rdf:rest N667152ad0a0346ad9c4b69392721dcc0
71 N0f86c3a1d92b4ca3a513278727041d0e schema:name Springer Nature
72 rdf:type schema:Organisation
73 N13d9c4c0c7dd4ce3b73899ad46e81791 rdf:first N692c2eeeac4047d99a525cd1fb7f2a04
74 rdf:rest N985f943baccd4dea974bfa6c0ce34393
75 N4b3412b5e8354ec68069899dd4433a8a rdf:first sg:person.013534566577.61
76 rdf:rest rdf:nil
77 N667152ad0a0346ad9c4b69392721dcc0 rdf:first Nfb90db313ad74916a2f01eafce774c54
78 rdf:rest N13d9c4c0c7dd4ce3b73899ad46e81791
79 N692c2eeeac4047d99a525cd1fb7f2a04 schema:familyName Păun
80 schema:givenName Gheorghe
81 rdf:type schema:Person
82 N7155f43e98324b2497138b7f19688959 schema:name dimensions_id
83 schema:value pub.1050084589
84 rdf:type schema:PropertyValue
85 N8149c4fe0dcc45f78552d41e0e1dcf3d schema:familyName Rozenberg
86 schema:givenName Grzegorz
87 rdf:type schema:Person
88 N985f943baccd4dea974bfa6c0ce34393 rdf:first N8149c4fe0dcc45f78552d41e0e1dcf3d
89 rdf:rest rdf:nil
90 Na108d72b214646f59da7ef0377205950 schema:isbn 978-3-642-60207-8
91 978-3-642-64304-0
92 schema:name Jewels are Forever
93 rdf:type schema:Book
94 Na1d779c10b174c81a9e656a942a96d11 schema:name doi
95 schema:value 10.1007/978-3-642-60207-8_23
96 rdf:type schema:PropertyValue
97 Nbe4a1d2572f84d71a318addb6ad50d80 schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 Nf7c6fc2aa69d4a83a39be1113f3e3993 rdf:first sg:person.010207617143.19
100 rdf:rest N4b3412b5e8354ec68069899dd4433a8a
101 Nfb90db313ad74916a2f01eafce774c54 schema:familyName Maurer
102 schema:givenName Hermann
103 rdf:type schema:Person
104 Nfe38c467034140b9ad0d5f804989b645 schema:familyName Karhumäki
105 schema:givenName Juhani
106 rdf:type schema:Person
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)


...