Ontology type: schema:Chapter
1999
AUTHORSWojciech Plandowski , Wojciech Rytter
ABSTRACTThe 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... »
PAGES262-272
Jewels are Forever
ISBN
978-3-642-64304-0
978-3-642-60207-8
http://scigraph.springernature.com/pub.10.1007/978-3-642-60207-8_23
DOIhttp://dx.doi.org/10.1007/978-3-642-60207-8_23
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1050084589
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
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 |