Recompression: Word Equations and Beyond View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Artur Jeż

ABSTRACT

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 ‘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... »

PAGES

12-26

Book

TITLE

Developments in Language Theory

ISBN

978-3-642-38770-8
978-3-642-38771-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-38771-5_2

DOI

http://dx.doi.org/10.1007/978-3-642-38771-5_2

DIMENSIONS

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


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/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

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-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

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-38771-5_2 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N6d26a786b2974c458e9c0b680e4d9d41
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema: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 ‘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.
7 schema:editor N49e0e08e5113470283ce3de4bf4e17cc
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8c6dce6455834d79ad76fee3773a44b8
12 schema:keywords PSPACE
13 SLP
14 applications
15 bottom
16 buildings
17 compression
18 equations
19 example
20 letter
21 local modification
22 modification
23 pairs
24 problem
25 proof
26 recompression
27 replacement
28 replacement of pairs
29 satisfiability
30 simple proof
31 solution
32 strings
33 technique
34 variables
35 word equations
36 schema:name Recompression: Word Equations and Beyond
37 schema:pagination 12-26
38 schema:productId Nd275dfe53517455f81c96b0bf35465a7
39 Neb56e3ccc26e41bcb9d747d9d7be64bf
40 schema:publisher N85c34435453145e2aaeadcb975a6ba01
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015581127
42 https://doi.org/10.1007/978-3-642-38771-5_2
43 schema:sdDatePublished 2022-05-20T07:48
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher N6089eaeadbc0408aa1c1308911b2832a
46 schema:url https://doi.org/10.1007/978-3-642-38771-5_2
47 sgo:license sg:explorer/license/
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N49e0e08e5113470283ce3de4bf4e17cc rdf:first Na319ec2fc3584439a5cd024e853bf124
51 rdf:rest Neae35d69c66940d2ad4e3fab2146ba9c
52 N6089eaeadbc0408aa1c1308911b2832a schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N6d26a786b2974c458e9c0b680e4d9d41 rdf:first sg:person.015252371751.76
55 rdf:rest rdf:nil
56 N85c34435453145e2aaeadcb975a6ba01 schema:name Springer Nature
57 rdf:type schema:Organisation
58 N8c6dce6455834d79ad76fee3773a44b8 schema:isbn 978-3-642-38770-8
59 978-3-642-38771-5
60 schema:name Developments in Language Theory
61 rdf:type schema:Book
62 Na319ec2fc3584439a5cd024e853bf124 schema:familyName Béal
63 schema:givenName Marie-Pierre
64 rdf:type schema:Person
65 Nd275dfe53517455f81c96b0bf35465a7 schema:name dimensions_id
66 schema:value pub.1015581127
67 rdf:type schema:PropertyValue
68 Nea6b2a9715a24e5890af7642705a3aae schema:familyName Carton
69 schema:givenName Olivier
70 rdf:type schema:Person
71 Neae35d69c66940d2ad4e3fab2146ba9c rdf:first Nea6b2a9715a24e5890af7642705a3aae
72 rdf:rest rdf:nil
73 Neb56e3ccc26e41bcb9d747d9d7be64bf schema:name doi
74 schema:value 10.1007/978-3-642-38771-5_2
75 rdf:type schema:PropertyValue
76 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
77 schema:name Mathematical Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
80 schema:name Pure Mathematics
81 rdf:type schema:DefinedTerm
82 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
83 schema:familyName Jeż
84 schema:givenName Artur
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
86 rdf:type schema:Person
87 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50-383, Wrocław, Poland
88 schema:name Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50-383, Wrocław, Poland
89 Max Planck Institute für Informatik, Campus E1 4, DE-66123, Saarbrücken, Germany
90 rdf:type schema:Organization
 




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


...