2013
AUTHORS ABSTRACTWe present the technique of local recompression on the example of word equations. The technique is based on local modification of variables (replacing X by aX or Xa) and replacement of pairs of letters appearing in the equation by a ‘fresh’ letter, which can be seen as a bottom-up building of an SLP (Straight-Line Programme) for the solution of the word equation, i.e. a compression.Using this technique we give a simple proof that satisfiability of word equations is in PSPACE. Furthermore we sketch the applications for some problems regarding the SLP compressed strings. More... »
PAGES12-26
Developments in Language Theory
ISBN
978-3-642-38770-8
978-3-642-38771-5
http://scigraph.springernature.com/pub.10.1007/978-3-642-38771-5_2
DOIhttp://dx.doi.org/10.1007/978-3-642-38771-5_2
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1015581127
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/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Pure Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie\u00a015, 50-383, Wroc\u0142aw, Poland",
"id": "http://www.grid.ac/institutes/grid.8505.8",
"name": [
"Max Planck Institute f\u00fcr Informatik, Campus E1 4, DE-66123, Saarbr\u00fccken, Germany",
"Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie\u00a015, 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"
}
],
"datePublished": "2013",
"datePublishedReg": "2013-01-01",
"description": "We present the technique of local recompression on the example of word equations. The technique is based on local modification of variables (replacing X by aX or Xa) and replacement of pairs of letters appearing in the equation by a \u2018fresh\u2019 letter, which can be seen as a bottom-up building of an SLP (Straight-Line Programme) for the solution of the word equation, i.e. a compression.Using this technique we give a simple proof that satisfiability of word equations is in PSPACE. Furthermore we sketch the applications for some problems regarding the SLP compressed strings.",
"editor": [
{
"familyName": "B\u00e9al",
"givenName": "Marie-Pierre",
"type": "Person"
},
{
"familyName": "Carton",
"givenName": "Olivier",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-38771-5_2",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-642-38770-8",
"978-3-642-38771-5"
],
"name": "Developments in Language Theory",
"type": "Book"
},
"keywords": [
"word equations",
"equations",
"simple proof",
"replacement of pairs",
"local modification",
"PSPACE",
"strings",
"technique",
"problem",
"solution",
"proof",
"satisfiability",
"variables",
"letter",
"applications",
"pairs",
"SLP",
"bottom",
"compression",
"modification",
"recompression",
"buildings",
"replacement",
"example"
],
"name": "Recompression: Word Equations and Beyond",
"pagination": "12-26",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1015581127"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-38771-5_2"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-38771-5_2",
"https://app.dimensions.ai/details/publication/pub.1015581127"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:48",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_54.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-38771-5_2"
}
]
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-38771-5_2'
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-38771-5_2'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38771-5_2'
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-38771-5_2'
This table displays all metadata directly associated to this object as RDF triples.
90 TRIPLES
23 PREDICATES
50 URIs
43 LITERALS
7 BLANK NODES