Day, Joel D.
[Verfasser:in];
Manea, Florin
[Verfasser:in];
Nowotka, Dirk
[Verfasser:in]
;
Joel D. Day and Florin Manea and Dirk Nowotka
[Mitwirkende:r]
Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
It is a long standing conjecture that the problem of deciding whether a quadratic word equation has a solution is in NP. It has also been conjectured that the length of a minimal solution to a quadratic equation is at most exponential in the length of the equation, with the latter conjecture implying the former. We show that both conjectures hold for some natural subclasses of quadratic equations, namely the classes of regular-reversed, k-ordered, and variable-sparse quadratic equations. We also discuss a connection of our techniques to the topic of unavoidable patterns, and the possibility of exploiting this connection to produce further similar results.