Word equation

Methods of solution

There is no "elementary" algorithm for determining whether a given word equation admits a solution. The algorithms mentioned above are all of theoretical interest, but they'll not help in solving a word equation by hand, for instance. There exist however a few methods that can sometimes help with this:

Length arguments

Because a solution ${\displaystyle h}$ to a word equation ${\displaystyle E}$ must unify its two sides, one can use the multiset of symbols occurring on either side of ${\displaystyle E}$ to deduce a linear equality in the lengths of the images of the unknowns. For instance, the form of ${\displaystyle xx\stackrel{\cdot }{=}y}$ implies that its solutions ${\displaystyle h}$ must satisfy ${\displaystyle |h(y)|=2|h(x)|}$, which narrows down the set of possible ${\displaystyle h}$ to check. Similar arguments can allow for a word equation ${\displaystyle E}$ to be "split up" into smaller ones if it can be deduced positions within the two sides of ${\displaystyle E}$ which must line up in all solutions of ${\displaystyle E}$. For instance, the midpoints of each side of ${\displaystyle xyyx\stackrel{\cdot }{=}uvvu}$ can be detected via a length argument, and hence that word equation can be split into the system ${\displaystyle \{\begin{array}{c}xy\stackrel{\cdot }{=}uv\\ yx\stackrel{\cdot }{=}vu\end{array}}$.

Appeal to periodicity

Another useful tool for reasoning about word equations is the Periodicity Lemma of Fine and Wilf, which describes what happens if a certain word has multiple periods (i.e., distances at which its letters repeat). Consider, for instance, the word equation ${\displaystyle E:=x^2{y}^2\stackrel{\cdot }{=}{z}^2}$. Suppose that ${\displaystyle (x,y,z)\mapsto (w_x,w_y,w_z)}$ is one of its solutions. Then ${\displaystyle w_x^2{w}_y^2=w_z^2}$. By taking a suitable conjugacy in this identity, one can infer that there exists some conjugate ${\displaystyle z^{\prime }}$ of ${\displaystyle z}$ which is such that ${\displaystyle z^{\prime 2}=w_x{w}_y^2{w}_x}$. Now a length argument permits for the midpoint of each side to be identified here, and it follows from this observation that ${\displaystyle w_x{w}_y=z^{\prime }=w_y{w}_x}$. Herein is the commutation equation, whence ${\displaystyle w_x}$ and ${\displaystyle w_y}$ are powers of a common word. Now the infinite words ${\displaystyle w_x^{\omega }}$ and ${\displaystyle w_z^{\omega }}$ have a common prefix of length ${\displaystyle |w_z^2|}$. Since ${\displaystyle |w_z^2|=2|w_z|\ge |w_z|+|w_x|\ge |w_z|+|w_x|-gcd(|z|,|x|)}$, the Periodicity Lemma can be applied. Its conclusion here is that ${\displaystyle w_z}$ and ${\displaystyle w_x}$ are powers of a common word too. Thus, every solution ${\displaystyle h}$ of ${\displaystyle E}$ maps ${\displaystyle x,y,}$ and ${\displaystyle z}$ to powers of a common word.

Nielsen transformations

Let ${\displaystyle E:=xu\stackrel{\cdot }{=}yv}$ be a word equation, such that ${\displaystyle x,y\in \mathrm{\Sigma }\cup \mathrm{\Xi }}$, and ${\displaystyle u,v\in (\mathrm{\Sigma }\cup \mathrm{\Xi }{)}^{\ast }}$. Here shall be presented a conceptually simple method (called Nielsen transformations algorithm, or Levi's Method.) to determine whether ${\displaystyle E}$ is soluble, with the caveat that the method terminates only on quadratic word equations (as defined above).

The idea of the algorithm is to "guess" how the lengths of ${\displaystyle x}$ and ${\displaystyle y}$ compare in some solution of ${\displaystyle E}$. Either ${\displaystyle |h(x)|>|h(y)|}$, ${\displaystyle |h(x)|<|h(y)|}$, or ${\displaystyle h(x)=h(y)}$. In the first case, one can apply the string-rewriting rule ${\displaystyle x\mapsto yx}$ to ${\displaystyle E}$, where ${\displaystyle x}$ (after the rewriting) is a new quantity whose meaning is "what's left of the old ${\displaystyle x}$ once ${\displaystyle y}$ is removed". Symmetrically, in the second case, one can apply the rule ${\displaystyle y\mapsto xy}$, and in the third case ${\displaystyle x\mapsto y}$. The present method actually makes all three guesses; for each of them (separately) it rewrites ${\displaystyle E}$ to account for the guess having been made.

By construction, there will be some cancellation at the start of ${\displaystyle E}$ after applying each string-rewriting rule. (For instance, applying ${\displaystyle x\mapsto ax}$ to the equation ${\displaystyle xab\stackrel{\cdot }{=}abx}$ yields ${\displaystyle axab\stackrel{\cdot }{=}abax}$, which cancels down to ${\displaystyle xab\stackrel{\cdot }{=}bax}$). The method always takes advantage of this cancellation; the hope is that it is enough to counteract the string-rewriting rule, which (in general) will have made the equation longer.

The algorithm thus amounts to exhaustively applying these transformations. It is natural to view the workings of the algorithm as the construction of a graph ${\displaystyle \mathcal{G}(E)}$, whose nodes are the reached equations, and edges are the transformations between them. If the trivial word equation ${\displaystyle \epsilon \stackrel{\cdot }{=}\epsilon }$, (where ${\displaystyle \epsilon }$ is the empty word) is ever encountered during this construction, then ${\displaystyle E}$ is surely solvable. Conversely, if ${\displaystyle E}$ is soluble, then ${\displaystyle \epsilon \stackrel{\cdot }{=}\epsilon }$ must appear in ${\displaystyle \mathcal{G}(E)}$. So, by this method (assuming ${\displaystyle \mathcal{G}(E)}$ is finite) it can be determined whether ${\displaystyle E}$ admits a solution.

Systems of word equations

One can define systems of word equations in the natural way. A solution of such a system ${\displaystyle S}$ is an assignment ${\displaystyle h}$ that solves simultaneously every equation in ${\displaystyle S}$. A natural extension is to consider Boolean formulas of word equations, in which also negation and disjunction is allowed. In fact, every system (and even every Boolean formula) of word equations, is equivalent to a single word equation. Thus, many results on word equations generalise immediately to such systems (resp. formulas). It must be said, however, that the transformation into a single word equation can introduce extra unknowns, and this is sometimes by necessity.

Two word equations (or systems thereof) are called equivalent if they have the same set of solutions. A system of word equations is called independent if it is not equivalent to any of its proper subsystems. Put another way, an independent system ${\displaystyle S}$ of word equations is one such that every ${\displaystyle E\in S}$ can be solved "independently", i.e., without solving any of the other ${\displaystyle E^{\prime }\in S}$. An interesting compactness theorem, usually bearing the name of Andrzej Ehrenfeucht, states that an infinite system of word equations, and with a finite number of unknowns, is necessarily equivalent to one of its finite subsystems. It follows that any independent system of word equations with a finite number of unknowns is itself finite.

Expressing formal languages and relations

Word equations can be used to characterise properties of (tuples of) words. For instance, a word ends in ${\displaystyle a}$ if and only if it is the image ${\displaystyle h(x)}$ in some solution of the word equation ${\displaystyle x\stackrel{\cdot }{=}ya}$. Similarly, two words commute if and only if they are the images ${\displaystyle h(x),h(y)}$ in some solution of the word equation ${\displaystyle xy\stackrel{\cdot }{=}yx}$. In this sense, word equations can be thought of as mechanisms for expressing formal languages, in analogy with automata and formal grammars. It is not known exactly which properties of (tuples of) words are expressible in via word equations in this way. In particular, to show that a relation is inexpressible by word equations is often quite challenging. (An example of an inexpressible property is "${\displaystyle x}$ is primitive").

It should be also noted that even characterising the solution set of a single word equation is complicated. Hmelevskii proved that, although the solutions to three-unknown constant-free equations can be given in terms of finite expressions with word and integer parameters, this is not true (in general) for four-unknown constant-free equations. In fact, ${\displaystyle xyz\stackrel{\cdot }{=}ztx}$ is an example of such a "non-parametrisable" word equation.

Extended theories and connections to string solving

One can augment word equations with other types of constraints on the values ${\displaystyle h(x)}$, ${\displaystyle x\in \mathrm{\Xi }}$. For instance, in 1968, Yuri Matiyasevich considered an extension of word equations by "length constraints" as a possible tool for showing the unsolvability of Hilbert's tenth problem. These length constraints amounted to linear inequalities in the unknowns ${\displaystyle |h(x)|}$, ${\displaystyle x\in \mathrm{\Xi }}$. Sometimes, allowing extra constraints (alongside word equations) leads to theories with undecidable solubility problems, but it is also possible to add less powerful constraints and end up with a theory that's still decidable. An example of the former type of constraint is requiring that some ${\displaystyle h(x),h(y)}$ should be Abelian equivalent (i.e., anagrams of one another); an example of the latter type is requiring that some ${\displaystyle h(x)}$ should belong to a given regular language ${\displaystyle L}$. For Matiyasevich's extension with the length constraints, the solubility problem still has open decidability status.

There has been recent interest in the theory of word equations (and more general theories based on it), from the practical point of view of those developing software verification tools called string solvers. These tools, which are increasingly popular, seek to solve algorithmically constraint satisfaction problems about strings. Such problems take the form of a set of constraints, which an unknown set of strings must satisfy. The string solver should then determine whether strings exist which satisfy all the given constraints. A typical goal of such a tool would be to guarantee that a particular piece of software was free from some string-related vulnerability, such as cross-site scripting or code injection.

The building blocks of the constraints used in these tools are the standard questions one might ask of strings, such as "is ${\displaystyle x}$ a substring of ${\displaystyle y}$?", "what is the length of string ${\displaystyle x}$?", and "what is the index of string ${\displaystyle x}$ in string ${\displaystyle y}$?". Ostensibly, these constraints can be modelled by theories based on word equations, and as such, string solver tools must be capable of dealing with these theories algorithmically, (at least in the subcase of those equations and formulas that actually arise in practice).

Relation to the defect effect

The defect theorem is a central result to combinatorics on words. It says that, if a set ${\displaystyle X}$ of words satisfies a nontrivial relation, then the words of ${\displaystyle X}$ can be (simultaneously) expressed as products of ${\displaystyle |X|-r}$ words, where ${\displaystyle r\ge 1}$. Such a set ${\displaystyle X}$ is then said to possess a "defect effect" of order ${\displaystyle r}$. Systems of word equations, (at least "nontrivial" ones), express the fact that a certain finite set of words, (namely the images ${\displaystyle h(x)}$ of the unknowns ${\displaystyle x\in \mathrm{\Xi }}$), satisfy some nontrivial relation(s). So it can be said that systems ${\displaystyle S}$ of word equations cause a defect effect in the sets of words ${\displaystyle X=\{h(x):x\in \mathrm{\Xi }\}}$ coming from solutions ${\displaystyle h}$ of ${\displaystyle S}$.

The defect effect caused by certain systems of word equations has been studied., and there exist some surprising results to this end showing that the "dimensionality properties" of sets of words are actually quite weak. For instance, it is known that there exists an independent system ${\displaystyle S}$ of equations of size ${\displaystyle \mathrm{\Omega }(n^2)}$, containing ${\displaystyle n}$ unknowns, which is such that ${\displaystyle S}$ causes only a defect effect of order ${\displaystyle 1}$.

Role within abstract algebra

There has been much research into formulating and solving equations within different structures of abstract algebra (e.g., groups and semigroups). Word equations, as presented here, are simply equations in free monoids. Equations in free semigroups are closely related to these; in fact, they are just word equations with the additional requirement that the solution ${\displaystyle h}$ is nonerasing. One can also consider equations in free groups, although the theory of such objects differs in many ways from the discussion presented here. Another result of Makanin's states that the solubility problem for equations in free groups is again decidable.