# One-Variable Word Equations in Linear Time

Ontology type: schema:ScholarlyArticle      Open Access: True

### Article Info

DATE

2014-09-11

AUTHORS ABSTRACT

In this paper we consider word equations with one-variable (and arbitrarily many occurrences of it). A recent technique of recompression, which is applicable to general word equations, is shown to be suitable also in this case. While in general case the recompression is nondeterministic in case of one-variable it becomes deterministic and its running time is O(n+#Xlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(n + \#_X \log n)$$\end{document}, where #X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\#_X$$\end{document} is the number of occurrences of the variable in the equation. This matches the previously best algorithm due to Dąbrowski and Plandowski. Then, using a couple of heuristics as well as more detailed time analysis, the running time is lowered to O(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(n)$$\end{document} in the RAM model. Unfortunately, no new properties of solutions are shown. More... »

PAGES

1-48

### References to SciGraph publications

• 2013. Approximation of Grammar-Based Compression via Recompression in COMBINATORIAL PATTERN MATCHING
• 2009-12-02. On Word Equations in One Variable in ALGORITHMICA
• 2004. Solving Two-Variable Word Equations in AUTOMATA, LANGUAGES AND PROGRAMMING
• 2013-01-18. The Complexity of Compressed Membership Problems for Finite Automata in THEORY OF COMPUTING SYSTEMS
• 2012. Faster Fully Compressed Pattern Matching by Recompression in AUTOMATA, LANGUAGES, AND PROGRAMMING
• 1993. Word equations with two variables in WORD EQUATIONS AND RELATED TOPICS
• 1997-02. Maintaining dynamic sequences under equality tests in polylogarithmic time in ALGORITHMICA
• 2001-06-13. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications in COMBINATORIAL PATTERN MATCHING
• 1998. Application of Lempel-Ziv encodings to the solution of word equations in AUTOMATA, LANGUAGES AND PROGRAMMING
• 1994. Efficient solving of the word equations in one variable in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1994
• 2011. Compressed Membership in Automata with Compressed Labels in COMPUTER SCIENCE – THEORY AND APPLICATIONS

TITLE

Algorithmica

ISSUE

1

VOLUME

74

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-014-9931-3

DOI

http://dx.doi.org/10.1007/s00453-014-9931-3

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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": "Institute of Computer Science, University of Wroc\u0142aw, ul.\u00a0Joliot-Curie 15, 50-383, Wroc\u0142aw, Poland",
"id": "http://www.grid.ac/institutes/grid.8505.8",
"name": [
"Max Planck Institute f\u00fc Informatik, 66123 Campus E1 4, Saarbr\u00fccken, Germany",
"Institute of Computer Science, University of Wroc\u0142aw, ul.\u00a0Joliot-Curie 15, 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"
}
],
"citation": [
{
"id": "sg:pub.10.1007/bf02522825",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007699916",
"https://doi.org/10.1007/bf02522825"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00224-013-9443-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1049189041",
"https://doi.org/10.1007/s00224-013-9443-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-56730-5_30",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012359530",
"https://doi.org/10.1007/3-540-56730-5_30"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-20712-9_21",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012277274",
"https://doi.org/10.1007/978-3-642-20712-9_21"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-58338-6_80",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012330089",
"https://doi.org/10.1007/3-540-58338-6_80"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-48194-x_17",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014677368",
"https://doi.org/10.1007/3-540-48194-x_17"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00453-009-9375-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1023253334",
"https://doi.org/10.1007/s00453-009-9375-3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-38905-4_17",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1022417385",
"https://doi.org/10.1007/978-3-642-38905-4_17"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-31594-7_45",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026589735",
"https://doi.org/10.1007/978-3-642-31594-7_45"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-27836-8_36",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036406748",
"https://doi.org/10.1007/978-3-540-27836-8_36"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0055097",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026190890",
"https://doi.org/10.1007/bfb0055097"
],
"type": "CreativeWork"
}
],
"datePublished": "2014-09-11",
"datePublishedReg": "2014-09-11",
"description": "In this paper we consider word equations with one-variable (and arbitrarily many occurrences of it). A recent technique of recompression, which is applicable to general word equations, is shown to be suitable also in this case. While in general case the recompression is nondeterministic in case of one-variable it becomes deterministic and its running time is O(n+#Xlogn)\\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}$$\\mathcal {O}(n + \\#_X \\log n)$$\\end{document}, where #X\\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}$$\\#_X$$\\end{document} is the number of occurrences of the variable in the equation. This matches the previously best algorithm due to D\u0105browski and Plandowski. Then, using a couple of heuristics as well as more detailed time analysis, the running time is lowered to O(n)\\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}$$\\mathcal {O}(n)$$\\end{document} in the RAM model. Unfortunately, no new properties of solutions are shown.",
"genre": "article",
"id": "sg:pub.10.1007/s00453-014-9931-3",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"word equations",
"One-Variable Word Equations",
"running time",
"general case",
"equations",
"detailed time analysis",
"one-variable",
"linear time",
"couple of heuristics",
"best algorithm",
"RAM model",
"new properties",
"number of occurrences",
"recent techniques",
"time analysis",
"Plandowski",
"algorithm",
"heuristics",
"solution",
"cases",
"model",
"variables",
"properties",
"time",
"technique",
"number",
"D\u0105browski",
"analysis",
"recompression",
"couples",
"occurrence",
"paper"
],
"name": "One-Variable Word Equations in Linear Time",
"pagination": "1-48",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1037587192"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-014-9931-3"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-014-9931-3",
"https://app.dimensions.ai/details/publication/pub.1037587192"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:29",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_625.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-014-9931-3"
}
]

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/s00453-014-9931-3'

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/s00453-014-9931-3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9931-3'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9931-3'

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

135 TRIPLES      22 PREDICATES      68 URIs      49 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-014-9931-3 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author Nd542267fb0a8437286b848ebbffa2bf0
4 schema:citation sg:pub.10.1007/3-540-48194-x_17
5 sg:pub.10.1007/3-540-56730-5_30
6 sg:pub.10.1007/3-540-58338-6_80
7 sg:pub.10.1007/978-3-540-27836-8_36
8 sg:pub.10.1007/978-3-642-20712-9_21
9 sg:pub.10.1007/978-3-642-31594-7_45
10 sg:pub.10.1007/978-3-642-38905-4_17
11 sg:pub.10.1007/bf02522825
12 sg:pub.10.1007/bfb0055097
13 sg:pub.10.1007/s00224-013-9443-6
14 sg:pub.10.1007/s00453-009-9375-3
15 schema:datePublished 2014-09-11
16 schema:datePublishedReg 2014-09-11
17 schema:description In this paper we consider word equations with one-variable (and arbitrarily many occurrences of it). A recent technique of recompression, which is applicable to general word equations, is shown to be suitable also in this case. While in general case the recompression is nondeterministic in case of one-variable it becomes deterministic and its running time is O(n+#Xlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(n + \#_X \log n)$$\end{document}, where #X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\#_X$$\end{document} is the number of occurrences of the variable in the equation. This matches the previously best algorithm due to Dąbrowski and Plandowski. Then, using a couple of heuristics as well as more detailed time analysis, the running time is lowered to O(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(n)$$\end{document} in the RAM model. Unfortunately, no new properties of solutions are shown.
18 schema:genre article
19 schema:inLanguage en
20 schema:isAccessibleForFree true
21 schema:isPartOf N4821151d41e04f9fa71fc4dcf7cd9b05
22 Nc8c91e9855b340108a09daea60b3ecbc
23 sg:journal.1047644
24 schema:keywords Dąbrowski
25 One-Variable Word Equations
26 Plandowski
27 RAM model
28 algorithm
29 analysis
30 best algorithm
31 cases
32 couple of heuristics
33 couples
34 detailed time analysis
35 equations
36 general case
37 heuristics
38 linear time
39 model
40 new properties
41 number
42 number of occurrences
43 occurrence
44 one-variable
45 paper
46 properties
47 recent techniques
48 recompression
49 running time
50 solution
51 technique
52 time
53 time analysis
54 variables
55 word equations
56 schema:name One-Variable Word Equations in Linear Time
57 schema:pagination 1-48
58 schema:productId N2df413371a234c089a98c977e3b5e6cd
59 Nb9677cb5869f495395e8e47e47398be6
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037587192
61 https://doi.org/10.1007/s00453-014-9931-3
62 schema:sdDatePublished 2022-05-20T07:29
64 schema:sdPublisher N9b046c2600ca44e5a46e47b7c07ea2a3
65 schema:url https://doi.org/10.1007/s00453-014-9931-3
67 sgo:sdDataset articles
68 rdf:type schema:ScholarlyArticle
69 N2df413371a234c089a98c977e3b5e6cd schema:name dimensions_id
70 schema:value pub.1037587192
71 rdf:type schema:PropertyValue
72 N4821151d41e04f9fa71fc4dcf7cd9b05 schema:issueNumber 1
73 rdf:type schema:PublicationIssue
74 N9b046c2600ca44e5a46e47b7c07ea2a3 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 Nb9677cb5869f495395e8e47e47398be6 schema:name doi
77 schema:value 10.1007/s00453-014-9931-3
78 rdf:type schema:PropertyValue
79 Nc8c91e9855b340108a09daea60b3ecbc schema:volumeNumber 74
80 rdf:type schema:PublicationVolume
81 Nd542267fb0a8437286b848ebbffa2bf0 rdf:first sg:person.015252371751.76
82 rdf:rest rdf:nil
83 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
84 schema:name Mathematical Sciences
85 rdf:type schema:DefinedTerm
86 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
87 schema:name Applied Mathematics
88 rdf:type schema:DefinedTerm
89 sg:journal.1047644 schema:issn 0178-4617
90 1432-0541
91 schema:name Algorithmica
92 schema:publisher Springer Nature
93 rdf:type schema:Periodical
94 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
95 schema:familyName Jeż
96 schema:givenName Artur
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
98 rdf:type schema:Person
99 sg:pub.10.1007/3-540-48194-x_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014677368
100 https://doi.org/10.1007/3-540-48194-x_17
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/3-540-56730-5_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012359530
103 https://doi.org/10.1007/3-540-56730-5_30
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/3-540-58338-6_80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012330089
106 https://doi.org/10.1007/3-540-58338-6_80
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/978-3-540-27836-8_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036406748
109 https://doi.org/10.1007/978-3-540-27836-8_36
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/978-3-642-20712-9_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012277274
112 https://doi.org/10.1007/978-3-642-20712-9_21
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/978-3-642-31594-7_45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026589735
115 https://doi.org/10.1007/978-3-642-31594-7_45
116 rdf:type schema:CreativeWork
117 sg:pub.10.1007/978-3-642-38905-4_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022417385
118 https://doi.org/10.1007/978-3-642-38905-4_17
119 rdf:type schema:CreativeWork
120 sg:pub.10.1007/bf02522825 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007699916
121 https://doi.org/10.1007/bf02522825
122 rdf:type schema:CreativeWork
123 sg:pub.10.1007/bfb0055097 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026190890
124 https://doi.org/10.1007/bfb0055097
125 rdf:type schema:CreativeWork
126 sg:pub.10.1007/s00224-013-9443-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049189041
127 https://doi.org/10.1007/s00224-013-9443-6
128 rdf:type schema:CreativeWork
129 sg:pub.10.1007/s00453-009-9375-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023253334
130 https://doi.org/10.1007/s00453-009-9375-3
131 rdf:type schema:CreativeWork
132 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50-383, Wrocław, Poland
133 schema:name Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50-383, Wrocław, Poland
134 Max Planck Institute fü Informatik, 66123 Campus E1 4, Saarbrücken, Germany
135 rdf:type schema:Organization

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

...