Abstract
In word equation problem we are given an equation u = v, where both u and v are words of letters and variables, and ask for a substitution of variables by words that equalizes the sides of the equation. This problem was first solved by Makanin and a different solution was proposed by Plandowski only 20 years later, his solution works in PSPACE, which is the best computational complexity bound known for this problem; on the other hand, the only known lowerbound is NPhardness. In both cases the algorithms (and proofs) employed nontrivial facts on word combinatorics.
In the paper I will present an application of a recent technique of recompression, which simplifies the known proofs and (slightly) lowers the complexity to linear nondeterministic space. The technique is based on employing simple compression rules (replacement of two letters ab by a new letter c, replacement of maximal repetitions of a by a new letter), and modifying the equations (replacing a variable X by bX or Xa) so that those operations are sound and complete. In particular, no combinatorial properties of strings are used.
The approach turns out to be quite robust and can be applied to various generalizations and related scenarios (context unification, i.e. equations over terms; equations over traces, i.e. partially ordered words; ...).
BibTeX  Entry
@InProceedings{je:LIPIcs:2020:11646,
author = {Artur Je?},
title = {{Solving Word Equations (And Other Unification Problems) by Recompression (Invited Talk)}},
booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
pages = {3:13:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771320},
ISSN = {18688969},
year = {2020},
volume = {152},
editor = {Maribel Fern{\'a}ndez and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11646},
URN = {urn:nbn:de:0030drops116468},
doi = {10.4230/LIPIcs.CSL.2020.3},
annote = {Keywords: word equation, context unification, equations in groups, compression}
}
Keywords: 

word equation, context unification, equations in groups, compression 
Collection: 

28th EACSL Annual Conference on Computer Science Logic (CSL 2020) 
Issue Date: 

2020 
Date of publication: 

06.01.2020 