caa a22 4500 44580453X CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00453-009-9375-3 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9375-3 On Word Equations in One Variable [Elektronische Daten] [Robert Dąbrowski, Wojciech Plandowski] For a word equation E of length n in one variable x occurring #x times in E a resolution algorithm of O(n+#xlog n) time complexity is presented here. This is the best result known and for the equations that feature $\#_{x}<\frac{n}{\log n}$ it yields time complexity of O(n) which is optimal. Additionally it is proven here that the set of solutions of any one-variable word equation is either of the form F or of the form F∪(uv)+ u where F is a set of O(log n) words and u, v are some words such that uv is a primitive word. Springer Science+Business Media, LLC, 2009 Word equation nationallicence Equation in free semigroup nationallicence Algorithm analysis and design nationallicence Computational complexity nationallicence Dąbrowski Robert Institute of Informatics, University of Warsaw, Banacha 2, 02-097, Warsaw, Poland aut Plandowski Wojciech Institute of Informatics, University of Warsaw, Banacha 2, 02-097, Warsaw, Poland aut Algorithmica Springer-Verlag 60/4(2011-08-01), 819-828 0178-4617 60:4<819 2011 60 453 https://doi.org/10.1007/s00453-009-9375-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9375-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dąbrowski Robert Institute of Informatics, University of Warsaw, Banacha 2, 02-097, Warsaw, Poland aut NATIONALLICENCE 700 1- Plandowski Wojciech Institute of Informatics, University of Warsaw, Banacha 2, 02-097, Warsaw, Poland aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/4(2011-08-01), 819-828 0178-4617 60:4<819 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer