Application of Lempel-Ziv encodings to the solution of word equations View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1998

AUTHORS

Wojciech Plandowski , Wojciech Rytter

ABSTRACT

One of the most intricate algorithms related to words is Makanin's algorithm solving word equations. The algorithm is very complicated and the complexity of the problem of solving word equations is not well understood. Word equations can be used to define various properties of strings, e.g. general versions of pattern-matching with variables. This paper is devoted to introduce a new approach and to study relations between Lempel-Ziv compressions and word equations. Instead of dealing with very long solutions we propose to deal with their Lempel-Ziv encodings. As our first main result we prove that each minimal solution of a word equation is highly compressible (exponentially compressible for long solutions) in terms of Lempel-Ziv encoding. A simple algorithm for solving word equations is derived. If the length of minimal solution is bounded by a singly exponential function (which is believed to be always true) then LZ encoding of each minimal solution is of a polynomial size (though the solution can be exponentially long) and solvability can be checked in nondeterministic polynomial time. As our second main result we prove that the solvability can be tested in polynomial deterministic time if the lengths of all variables are given in binary. We show also that lexicographically first solution for given lengths of variables is highly compressible in terms of Lempel-Ziv encodings. More... »

PAGES

731-742

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0055097

DOI

http://dx.doi.org/10.1007/bfb0055097

DIMENSIONS

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


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": "Turku Centre for Computer Science and Department of Mathematics, Turku University, 20 014, Turku, Finland", 
          "id": "http://www.grid.ac/institutes/grid.1374.1", 
          "name": [
            "Turku Centre for Computer Science and Department of Mathematics, Turku University, 20 014, Turku, Finland"
          ], 
          "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": "1998", 
    "datePublishedReg": "1998-01-01", 
    "description": "One of the most intricate algorithms related to words is Makanin's algorithm solving word equations. The algorithm is very complicated and the complexity of the problem of solving word equations is not well understood. Word equations can be used to define various properties of strings, e.g. general versions of pattern-matching with variables. This paper is devoted to introduce a new approach and to study relations between Lempel-Ziv compressions and word equations. Instead of dealing with very long solutions we propose to deal with their Lempel-Ziv encodings. As our first main result we prove that each minimal solution of a word equation is highly compressible (exponentially compressible for long solutions) in terms of Lempel-Ziv encoding. A simple algorithm for solving word equations is derived. If the length of minimal solution is bounded by a singly exponential function (which is believed to be always true) then LZ encoding of each minimal solution is of a polynomial size (though the solution can be exponentially long) and solvability can be checked in nondeterministic polynomial time. As our second main result we prove that the solvability can be tested in polynomial deterministic time if the lengths of all variables are given in binary. We show also that lexicographically first solution for given lengths of variables is highly compressible in terms of Lempel-Ziv encodings.", 
    "editor": [
      {
        "familyName": "Larsen", 
        "givenName": "Kim G.", 
        "type": "Person"
      }, 
      {
        "familyName": "Skyum", 
        "givenName": "Sven", 
        "type": "Person"
      }, 
      {
        "familyName": "Winskel", 
        "givenName": "Glynn", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0055097", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64781-2", 
        "978-3-540-68681-1"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "word equations", 
      "minimal solutions", 
      "Makanin's algorithm", 
      "first main result", 
      "second main result", 
      "properties of strings", 
      "nondeterministic polynomial time", 
      "long solutions", 
      "main results", 
      "equations", 
      "general version", 
      "deterministic time", 
      "solvability", 
      "polynomial time", 
      "simple algorithm", 
      "length of variables", 
      "first solution", 
      "polynomial size", 
      "intricate algorithms", 
      "algorithm", 
      "exponential function", 
      "solution", 
      "new approach", 
      "variables", 
      "Lempel-Ziv compression", 
      "terms", 
      "strings", 
      "problem", 
      "complexity", 
      "LZ", 
      "binaries", 
      "version", 
      "properties", 
      "applications", 
      "length", 
      "approach", 
      "results", 
      "function", 
      "encoding", 
      "time", 
      "size", 
      "relation", 
      "compression", 
      "words", 
      "paper"
    ], 
    "name": "Application of Lempel-Ziv encodings to the solution of word equations", 
    "pagination": "731-742", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026190890"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0055097"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0055097", 
      "https://app.dimensions.ai/details/publication/pub.1026190890"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:28", 
    "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_165.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0055097"
  }
]
 

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

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

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0055097'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0055097'


 

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

126 TRIPLES      23 PREDICATES      71 URIs      64 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0055097 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N27eb99b583154e9383662ed0dcf3675d
4 schema:datePublished 1998
5 schema:datePublishedReg 1998-01-01
6 schema:description One of the most intricate algorithms related to words is Makanin's algorithm solving word equations. The algorithm is very complicated and the complexity of the problem of solving word equations is not well understood. Word equations can be used to define various properties of strings, e.g. general versions of pattern-matching with variables. This paper is devoted to introduce a new approach and to study relations between Lempel-Ziv compressions and word equations. Instead of dealing with very long solutions we propose to deal with their Lempel-Ziv encodings. As our first main result we prove that each minimal solution of a word equation is highly compressible (exponentially compressible for long solutions) in terms of Lempel-Ziv encoding. A simple algorithm for solving word equations is derived. If the length of minimal solution is bounded by a singly exponential function (which is believed to be always true) then LZ encoding of each minimal solution is of a polynomial size (though the solution can be exponentially long) and solvability can be checked in nondeterministic polynomial time. As our second main result we prove that the solvability can be tested in polynomial deterministic time if the lengths of all variables are given in binary. We show also that lexicographically first solution for given lengths of variables is highly compressible in terms of Lempel-Ziv encodings.
7 schema:editor Ne682b716838543fd8229cca200601e56
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N82079f5a33324c31a45bc51e84bca7c9
12 schema:keywords LZ
13 Lempel-Ziv compression
14 Makanin's algorithm
15 algorithm
16 applications
17 approach
18 binaries
19 complexity
20 compression
21 deterministic time
22 encoding
23 equations
24 exponential function
25 first main result
26 first solution
27 function
28 general version
29 intricate algorithms
30 length
31 length of variables
32 long solutions
33 main results
34 minimal solutions
35 new approach
36 nondeterministic polynomial time
37 paper
38 polynomial size
39 polynomial time
40 problem
41 properties
42 properties of strings
43 relation
44 results
45 second main result
46 simple algorithm
47 size
48 solution
49 solvability
50 strings
51 terms
52 time
53 variables
54 version
55 word equations
56 words
57 schema:name Application of Lempel-Ziv encodings to the solution of word equations
58 schema:pagination 731-742
59 schema:productId N0a77f5820d404939bb57db236709a22a
60 Nd8253ae245b94dab87604f9e46bb6020
61 schema:publisher Nbdb1f5461ed64d27b9831165ef60ef96
62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026190890
63 https://doi.org/10.1007/bfb0055097
64 schema:sdDatePublished 2022-06-01T22:28
65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
66 schema:sdPublisher Nc62132e700fa47be9179ad6145a1aefb
67 schema:url https://doi.org/10.1007/bfb0055097
68 sgo:license sg:explorer/license/
69 sgo:sdDataset chapters
70 rdf:type schema:Chapter
71 N023577960d154d30a22a566f92f89342 rdf:first N61e442ac294949c89f3bc607d308b385
72 rdf:rest Nba13c84834e246ed9226ef077773c146
73 N0a77f5820d404939bb57db236709a22a schema:name doi
74 schema:value 10.1007/bfb0055097
75 rdf:type schema:PropertyValue
76 N27eb99b583154e9383662ed0dcf3675d rdf:first sg:person.010207617143.19
77 rdf:rest Na0f0bbad38cd4b588a6f12db5e0b2f13
78 N51788f4ac0fb464a873f10adfc8a3623 schema:familyName Winskel
79 schema:givenName Glynn
80 rdf:type schema:Person
81 N61e442ac294949c89f3bc607d308b385 schema:familyName Skyum
82 schema:givenName Sven
83 rdf:type schema:Person
84 N82079f5a33324c31a45bc51e84bca7c9 schema:isbn 978-3-540-64781-2
85 978-3-540-68681-1
86 schema:name Automata, Languages and Programming
87 rdf:type schema:Book
88 Na0f0bbad38cd4b588a6f12db5e0b2f13 rdf:first sg:person.013534566577.61
89 rdf:rest rdf:nil
90 Na38bc02166b142bebf6b5ad31d3d2ee9 schema:familyName Larsen
91 schema:givenName Kim G.
92 rdf:type schema:Person
93 Nba13c84834e246ed9226ef077773c146 rdf:first N51788f4ac0fb464a873f10adfc8a3623
94 rdf:rest rdf:nil
95 Nbdb1f5461ed64d27b9831165ef60ef96 schema:name Springer Nature
96 rdf:type schema:Organisation
97 Nc62132e700fa47be9179ad6145a1aefb schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 Nd8253ae245b94dab87604f9e46bb6020 schema:name dimensions_id
100 schema:value pub.1026190890
101 rdf:type schema:PropertyValue
102 Ne682b716838543fd8229cca200601e56 rdf:first Na38bc02166b142bebf6b5ad31d3d2ee9
103 rdf:rest N023577960d154d30a22a566f92f89342
104 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
105 schema:name Mathematical Sciences
106 rdf:type schema:DefinedTerm
107 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
108 schema:name Pure Mathematics
109 rdf:type schema:DefinedTerm
110 sg:person.010207617143.19 schema:affiliation grid-institutes:grid.1374.1
111 schema:familyName Plandowski
112 schema:givenName Wojciech
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010207617143.19
114 rdf:type schema:Person
115 sg:person.013534566577.61 schema:affiliation grid-institutes:grid.10025.36
116 schema:familyName Rytter
117 schema:givenName Wojciech
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013534566577.61
119 rdf:type schema:Person
120 grid-institutes:grid.10025.36 schema:alternateName Department of Computer Science, University of Liverpool, UK
121 schema:name Department of Computer Science, University of Liverpool, UK
122 Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warszawa, Poland
123 rdf:type schema:Organization
124 grid-institutes:grid.1374.1 schema:alternateName Turku Centre for Computer Science and Department of Mathematics, Turku University, 20 014, Turku, Finland
125 schema:name Turku Centre for Computer Science and Department of Mathematics, Turku University, 20 014, Turku, Finland
126 rdf:type schema:Organization
 




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


...