Ontology type: schema:ScholarlyArticle Open Access: True
2014-09-11
AUTHORS ABSTRACTIn 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... »
PAGES1-48
http://scigraph.springernature.com/pub.10.1007/s00453-014-9931-3
DOIhttp://dx.doi.org/10.1007/s00453-014-9931-3
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1037587192
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": "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",
"volumeNumber": "74"
}
],
"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",
"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/article/article_625.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-014-9931-3"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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