Recompression: Technique for Word Equations and Compressed Data View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2020-02-25

AUTHORS

Artur Jeż

ABSTRACT

In this talk I will present the recompression technique on the running example of word equations. In word equation problem we are given an equation \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u = v$$\end{document}, where both u and v are words of letters and variables, and ask for a substitution of variables by words that equalizes the sides of the equation. The recompression technique is based on employing simple compression rules (replacement of two letters ab by a new letter c, replacement of maximal repetitions of a by a new letter), and modifying the equations (replacing a variable X by bX or Xa) so that those operations are sound and complete. The simple analysis focuses on the size of the instance and not on the combinatorial properties of words that are used. The recompression-based algorithm for word equations runs in nondeterministic linear space.The approach turned out to be quite robust and can be applied to various generalized, simplified and related problems, in particular, to problems in the area of grammar compressed words. I will comment on some of those applications. More... »

PAGES

44-67

Book

TITLE

Language and Automata Theory and Applications

ISBN

978-3-030-40607-3
978-3-030-40608-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-40608-0_4

DOI

http://dx.doi.org/10.1007/978-3-030-40608-0_4

DIMENSIONS

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


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/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Wroc\u0142aw, Joliot-Curie 15, 50383, Wroc\u0142aw, Poland", 
          "id": "http://www.grid.ac/institutes/grid.8505.8", 
          "name": [
            "University of Wroc\u0142aw, Joliot-Curie 15, 50383, 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": "2020-02-25", 
    "datePublishedReg": "2020-02-25", 
    "description": "In this talk I will present the recompression technique on the running example of word equations. In word equation problem we are given an equation \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$u = v$$\\end{document}, where both u and v are words of letters and variables, and ask for a substitution of variables by words that equalizes the sides of the equation. The recompression technique is based on employing simple compression rules (replacement of two letters ab by\u00a0a\u00a0new letter c, replacement of maximal repetitions of a by a new letter), and modifying the equations (replacing a variable X by bX or Xa) so that those operations are sound and complete. The simple analysis focuses on\u00a0the size of the instance and not on the combinatorial properties of words that are used. The recompression-based algorithm for word equations runs in nondeterministic linear space.The approach turned out to be quite robust and can be applied to various generalized, simplified and related problems, in particular, to problems in the area of grammar compressed words. I will comment on some of\u00a0those applications.", 
    "editor": [
      {
        "familyName": "Leporati", 
        "givenName": "Alberto", 
        "type": "Person"
      }, 
      {
        "familyName": "Mart\u00edn-Vide", 
        "givenName": "Carlos", 
        "type": "Person"
      }, 
      {
        "familyName": "Shapira", 
        "givenName": "Dana", 
        "type": "Person"
      }, 
      {
        "familyName": "Zandron", 
        "givenName": "Claudio", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-40608-0_4", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-030-40607-3", 
        "978-3-030-40608-0"
      ], 
      "name": "Language and Automata Theory and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "word equations", 
      "recompression technique", 
      "simple compression rules", 
      "equation problem", 
      "linear space", 
      "substitution of variables", 
      "combinatorial properties", 
      "nondeterministic linear space", 
      "equations", 
      "talk I", 
      "related problems", 
      "compression rules", 
      "Compressed Data", 
      "simple analysis", 
      "problem", 
      "variables", 
      "algorithm", 
      "space", 
      "technique", 
      "properties", 
      "applications", 
      "approach", 
      "instances", 
      "rules", 
      "operation", 
      "letter", 
      "size", 
      "analysis", 
      "data", 
      "side", 
      "words", 
      "areas of grammar", 
      "area", 
      "substitution", 
      "grammar", 
      "example"
    ], 
    "name": "Recompression: Technique for Word Equations and Compressed Data", 
    "pagination": "44-67", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1125101276"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-40608-0_4"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-40608-0_4", 
      "https://app.dimensions.ai/details/publication/pub.1125101276"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:41", 
    "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_105.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-40608-0_4"
  }
]
 

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-030-40608-0_4'

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-030-40608-0_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-40608-0_4'

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-030-40608-0_4'


 

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

111 TRIPLES      23 PREDICATES      61 URIs      54 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-40608-0_4 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author Ne540becfabcd4294a79a92e966f8f4ff
4 schema:datePublished 2020-02-25
5 schema:datePublishedReg 2020-02-25
6 schema:description In this talk I will present the recompression technique on the running example of word equations. In word equation problem we are given an equation \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u = v$$\end{document}, where both u and v are words of letters and variables, and ask for a substitution of variables by words that equalizes the sides of the equation. The recompression technique is based on employing simple compression rules (replacement of two letters ab by a new letter c, replacement of maximal repetitions of a by a new letter), and modifying the equations (replacing a variable X by bX or Xa) so that those operations are sound and complete. The simple analysis focuses on the size of the instance and not on the combinatorial properties of words that are used. The recompression-based algorithm for word equations runs in nondeterministic linear space.The approach turned out to be quite robust and can be applied to various generalized, simplified and related problems, in particular, to problems in the area of grammar compressed words. I will comment on some of those applications.
7 schema:editor Nd0998a028f114819a18469681f900da7
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ne73b66172b794043bf3e8c84237a4c9b
12 schema:keywords Compressed Data
13 algorithm
14 analysis
15 applications
16 approach
17 area
18 areas of grammar
19 combinatorial properties
20 compression rules
21 data
22 equation problem
23 equations
24 example
25 grammar
26 instances
27 letter
28 linear space
29 nondeterministic linear space
30 operation
31 problem
32 properties
33 recompression technique
34 related problems
35 rules
36 side
37 simple analysis
38 simple compression rules
39 size
40 space
41 substitution
42 substitution of variables
43 talk I
44 technique
45 variables
46 word equations
47 words
48 schema:name Recompression: Technique for Word Equations and Compressed Data
49 schema:pagination 44-67
50 schema:productId N35eeff96faed4609b942f91716fae95f
51 Nccb6a3a3b356442688053a27bf53906d
52 schema:publisher N52b653368cb54178bb9ba4845471c319
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1125101276
54 https://doi.org/10.1007/978-3-030-40608-0_4
55 schema:sdDatePublished 2022-05-20T07:41
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Nf3d05c12c89b430bb933469f09cc8703
58 schema:url https://doi.org/10.1007/978-3-030-40608-0_4
59 sgo:license sg:explorer/license/
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N19446f3feee240a987cf8ec4b9fe072f schema:familyName Martín-Vide
63 schema:givenName Carlos
64 rdf:type schema:Person
65 N35eeff96faed4609b942f91716fae95f schema:name dimensions_id
66 schema:value pub.1125101276
67 rdf:type schema:PropertyValue
68 N52b653368cb54178bb9ba4845471c319 schema:name Springer Nature
69 rdf:type schema:Organisation
70 N7578a6aaa76e48eb8cd817b089584b73 schema:familyName Shapira
71 schema:givenName Dana
72 rdf:type schema:Person
73 N7a0c93db47bf47e7bf0461d64911d591 rdf:first N7578a6aaa76e48eb8cd817b089584b73
74 rdf:rest N9ab18db77edb453fb1480d26e867977b
75 N976e28fbb7094fe58efb7dbde29e80a5 rdf:first N19446f3feee240a987cf8ec4b9fe072f
76 rdf:rest N7a0c93db47bf47e7bf0461d64911d591
77 N9ab18db77edb453fb1480d26e867977b rdf:first Nbe552b7fcf394ec281ef8051d2961c74
78 rdf:rest rdf:nil
79 Nb0798ada1a59479caefa85ef16a8bb07 schema:familyName Leporati
80 schema:givenName Alberto
81 rdf:type schema:Person
82 Nbe552b7fcf394ec281ef8051d2961c74 schema:familyName Zandron
83 schema:givenName Claudio
84 rdf:type schema:Person
85 Nccb6a3a3b356442688053a27bf53906d schema:name doi
86 schema:value 10.1007/978-3-030-40608-0_4
87 rdf:type schema:PropertyValue
88 Nd0998a028f114819a18469681f900da7 rdf:first Nb0798ada1a59479caefa85ef16a8bb07
89 rdf:rest N976e28fbb7094fe58efb7dbde29e80a5
90 Ne540becfabcd4294a79a92e966f8f4ff rdf:first sg:person.015252371751.76
91 rdf:rest rdf:nil
92 Ne73b66172b794043bf3e8c84237a4c9b schema:isbn 978-3-030-40607-3
93 978-3-030-40608-0
94 schema:name Language and Automata Theory and Applications
95 rdf:type schema:Book
96 Nf3d05c12c89b430bb933469f09cc8703 schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
98 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
99 schema:name Mathematical Sciences
100 rdf:type schema:DefinedTerm
101 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
102 schema:name Applied Mathematics
103 rdf:type schema:DefinedTerm
104 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
105 schema:familyName Jeż
106 schema:givenName Artur
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
108 rdf:type schema:Person
109 grid-institutes:grid.8505.8 schema:alternateName University of Wrocław, Joliot-Curie 15, 50383, Wrocław, Poland
110 schema:name University of Wrocław, Joliot-Curie 15, 50383, Wrocław, Poland
111 rdf:type schema:Organization
 




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


...