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 Needd70385a6445908e4c2d916759f6dc
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 Nb058be47b86a4549af76e00f1fe49f3e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nf6d1fc4aaee04610a71a83dba27f28db
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 N029e5a69ef704846a4b75471ab846723
60 Ncdb1545642e94f469b6eb527bad7f620
61 schema:publisher N5090fa8fe9ca45e2bb37c38524ee747f
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 Nd2d1695bde2647acb98e07f255bb92cd
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 N029e5a69ef704846a4b75471ab846723 schema:name doi
72 schema:value 10.1007/bfb0055097
73 rdf:type schema:PropertyValue
74 N46d86e897b1249378fc6d69aa085d7f1 schema:familyName Larsen
75 schema:givenName Kim G.
76 rdf:type schema:Person
77 N5090fa8fe9ca45e2bb37c38524ee747f schema:name Springer Nature
78 rdf:type schema:Organisation
79 N5fe3e78b5c6347f086f51013a16289b1 rdf:first sg:person.013534566577.61
80 rdf:rest rdf:nil
81 N6e1121255d924d0296684810876dd52c rdf:first Nc6adf3f840f04253a76e3fc7448c401c
82 rdf:rest rdf:nil
83 N78457734d9b34650a07ec644f2375ea7 rdf:first Nb5897f0df08d4baf98e2adfa95e5419e
84 rdf:rest N6e1121255d924d0296684810876dd52c
85 Nb058be47b86a4549af76e00f1fe49f3e rdf:first N46d86e897b1249378fc6d69aa085d7f1
86 rdf:rest N78457734d9b34650a07ec644f2375ea7
87 Nb5897f0df08d4baf98e2adfa95e5419e schema:familyName Skyum
88 schema:givenName Sven
89 rdf:type schema:Person
90 Nc6adf3f840f04253a76e3fc7448c401c schema:familyName Winskel
91 schema:givenName Glynn
92 rdf:type schema:Person
93 Ncdb1545642e94f469b6eb527bad7f620 schema:name dimensions_id
94 schema:value pub.1026190890
95 rdf:type schema:PropertyValue
96 Nd2d1695bde2647acb98e07f255bb92cd schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
98 Needd70385a6445908e4c2d916759f6dc rdf:first sg:person.010207617143.19
99 rdf:rest N5fe3e78b5c6347f086f51013a16289b1
100 Nf6d1fc4aaee04610a71a83dba27f28db schema:isbn 978-3-540-64781-2
101 978-3-540-68681-1
102 schema:name Automata, Languages and Programming
103 rdf:type schema:Book
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)


...