One-Variable Word Equations in Linear Time View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2014-09-11

AUTHORS

Artur Jeż

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
  • 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: 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

    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
    63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    64 schema:sdPublisher N9b046c2600ca44e5a46e47b7c07ea2a3
    65 schema:url https://doi.org/10.1007/s00453-014-9931-3
    66 sgo:license sg:explorer/license/
    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)


    ...