  Satisfiability of word equations is an important problem in the intersection
of formal languages and algebra: Given two sequences consisting of letters and
variables we are to decide whether there is a substitution for the variables
that turns this equation into true equality of strings. The exact computational
complexity of this problem remains unknown, with the best lower and upper
bounds being, respectively, NP and PSPACE. Recently, the novel technique of
recompression was applied to this problem, simplifying the known proofs and
lowering the space complexity to (nondeterministic) O(n log n). In this paper
we show that satisfiability of word equations is in nondeterministic linear
space, thus the language of satisfiable word equations is context-sensitive,
and by the famous Immerman-Szelepcsenyi theorem: the language of unsatisfiable
word equations is also context-sensitive. We use the known recompression-based
algorithm and additionally employ Huffman coding for letters. The proof,
however, uses analysis of how the fragments of the equation depend on each
other as well as a new strategy for nondeterministic choices of the algorithm,
which uses several new ideas to limit the space occupied by the letters.
