Word equation

A word equation is a formal equality $E:=u{\overset {\cdot }{=}}v$ between a pair of words $u$ and $v$, each over an alphabet $\Sigma \cup \Xi$ comprising both constants (c.f. $\Sigma$) and unknowns (c.f. $\Xi$).  An assignment $h$ of constant words to the unknowns of $E$ is said to solve $E$ if it maps both sides of $E$ to identical words. In other words, the solutions of $E$ are those morphisms $h:(\Sigma \cup \Xi )^{*}\to \Sigma ^{*}$ whose restriction to $\Sigma$ is the identity map, and which satisfy $h(u)=h(v)$. Word equations are a central object in combinatorics on words; they play an analogous role in this area as do Diophantine equations in number theory. One stark difference is that Diophantine equations have an undecidable solubility problem, whereas the analogous problem for word equations is decidable.

A classical example of a word equation is the commutation equation $xw{\overset {\cdot }{=}}wx$, in which $x$ is an unknown and $w$ is a constant word. It is well-known that the solutions of the commutation equation are exactly those morphisms $h$ mapping $x$ to some power of $w$. Another example is the conjugacy equation $xz{\overset {\cdot }{=}}zy$, in which $x,y,$ and $z$ are all unknowns. The solutions of this equation are precisely those morphisms $h$ sending $x$ and $y$ to conjugate words, with the image $h(z)$ being filled in as appropriate.

Many subclasses of word equations have been introduced, some of which include:

• constant-free equations, which are those $u{\overset {\cdot }{=}}v$ such that $u,v$ comprise unknowns only. Such equations have a trivial solution wherein all their unknowns are erased; as such, they are usually studied over free semigroups.
• quadratic equations, which are those containing each of their unknowns at most twice. This is exactly the class of word equations on which the Nielsen Transformations algorithm (c.f. below) terminates.
• word equations in one unknown, which can be checked for their solubility in linear time.

History

The study of word equations was initiated by Willard Quine as early as 1946. Quine proved that the first-order theory of word equations is essentially equivalent to the first-order theory of arithmetic. In 1954, Andrey Markov proposed the solubility problem for word equations: decide whether a given word equation admits a solution. For a long time, it was hoped that this problem was undecidable. One reason for this is that it was expected, (incorrectly, it turns out), that word equations might provide an intermediary step between Hilbert's Tenth Problem and the undecidable problems relating to Turing machines.

Gennady Makanin, who introduced Makanin's algorithm.

Further contributions were made in the early 1970s with the work of André Lentin and Juri Ilich Hmelevskii. In 1976, Gennady Makanin introduced a method by which it could be determined whether any given word equation admitted a solution. That this procedure, which has come to be known as Makanin's algorithm, exists is very difficult to prove, and it is one of the most celebrated results in combinatorics on words. Makanin's algorithm is considered to be a one of the most conceptually difficult existing in literature, and it is also highly intractable, requiring (in its initial formulation) triply exponential time. Thus, there were many attempts to improve upon it. In 1999, Wojciech Plandowski introduced a novel algorithm, showing that the solubility problem for word equations is in PSPACE.

In 2006, Plandowski and Wojciech Rytter showed that minimal solutions of word equations are highly (i.e., exponentially) compressible using Lempel-Ziv encoding. It is conjectured that the length of a minimal solution of a word equation $E$ is (at most) singly exponential in the length $|E|$ of $E$. If this conjecture is true, then Plandowski and Rytter's result yields a straightforward "guess-and-verify" NP algorithm for the solubility problem: they show that a solution $h$ can be verified whilst working only with its LZ-compressed representation $LZ(h)$, and the conjecture being true would imply that $LZ(h)$ has size polynomial in $|E|$. As it stands, the last part of the complexity analysis -- the question as to whether solving word equations is NP-complete -- remains open. (NP-hardness follows immediately from the fact that solving word equations generalises the NP-complete problem of pattern matching).

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

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 $E:=x^{2}y^{2}{\overset {\cdot }{=}}z^{2}$. Suppose that $(x,y,z)\mapsto (w_{x},w_{y},w_{z})$ is one of its solutions. Then $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 $z'$ of $z$ which is such that $z'^{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 $w_{x}w_{y}=z'=w_{y}w_{x}$. Herein is the commutation equation, whence $w_{x}$ and $w_{y}$ are powers of a common word. Now the infinite words $w_{x}^{\omega }$ and $w_{z}^{\omega }$ have a common prefix of length $|w_{z}^{2}|$. Since $|w_{z}^{2}|=2|w_{z}|\geq |w_{z}|+|w_{x}|\geq |w_{z}|+|w_{x}|-\gcd(|z|,|x|)$, the Periodicity Lemma can be applied. Its conclusion here is that $w_{z}$ and $w_{x}$ are powers of a common word too. Thus, every solution $h$ of $E$ maps $x,y,$ and $z$ to powers of a common word.

Nielsen transformations

The workings of the Nielsen transformations algorithm on the word equation $XaY{\overset {\cdot }{=}}YbX$. The trivial word equation was not reached, implying the equation’s insolubility.

Let $E:=xu{\overset {\cdot }{=}}yv$ be a word equation, such that $x,y\in \Sigma \cup \Xi$, and $u,v\in (\Sigma \cup \Xi )^{*}$. Here shall be presented a conceptually simple method (called Nielsen transformations algorithm, or Levi's Method.) to determine whether $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 $x$ and $y$ compare in some solution of $E$. Either $|h(x)|>|h(y)|$, $|h(x)|<|h(y)|$, or $h(x)=h(y)$. In the first case, one can apply the string-rewriting rule $x\mapsto yx$ to $E$, where $x$ (after the rewriting) is a new quantity whose meaning is "what's left of the old $x$ once $y$ is removed". Symmetrically, in the second case, one can apply the rule $y\mapsto xy$, and in the third case $x\mapsto y$. The present method actually makes all three guesses; for each of them (separately) it rewrites $E$ to account for the guess having been made.

By construction, there will be some cancellation at the start of $E$ after applying each string-rewriting rule. (For instance, applying $x\mapsto ax$ to the equation $xab{\overset {\cdot }{=}}abx$ yields $axab{\overset {\cdot }{=}}abax$, which cancels down to $xab{\overset {\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 ${\mathcal {G}}(E)$, whose nodes are the reached equations, and edges are the transformations between them. If the trivial word equation $\varepsilon {\overset {\cdot }{=}}\varepsilon$, (where $\varepsilon$ is the empty word) is ever encountered during this construction, then $E$ is surely solvable. Conversely, if $E$ is soluble, then $\varepsilon {\overset {\cdot }{=}}\varepsilon$ must appear in ${\mathcal {G}}(E)$. So, by this method (assuming ${\mathcal {G}}(E)$ is finite) it can be determined whether $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 $S$ is a morphism $h$ that solves simultaneously every equation in $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 $S$ of word equations is one such that every $E\in S$ can be solved "independently", i.e., without solving any of the other $E'\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 $a$ if and only if it is the image $h(x)$ in some solution of the word equation $x{\overset {\cdot }{=}}ya$. Similarly, two words commute if and only if they are the images $h(x),h(y)$ in some solution of the word equation $xy{\overset {\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 "$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, $xyz{\overset {\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 $h(x)$, $x\in \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 $|h(x)|$, $x\in \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 $h(x),h(y)$ should be Abelian equivalent (i.e., anagrams of one another); an example of the latter type is requiring that some $h(x)$ should belong to a given regular language $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 $x$ a substring of $y$?", "what is the length of string $x$?", and "what is the index of string $x$ in string $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 $X$ of words satisfies a nontrivial relation, then the words of $X$ can be (simultaneously) expressed as powers of $|X|-r$ words, where $r\geq 1$. Such a set $X$ is then said to possess a "defect effect" of order $r$. Systems of word equations, (at least "nontrivial" ones), express the fact that a certain finite set of words, (namely the images $h(x)$ of the unknowns $x\in \Xi$), satisfy some nontrivial relation(s). So it can be said that systems $S$ of word equations cause a defect effect in the sets of words $X=\{h(x):x\in \Xi \}$ coming from solutions $h$ of $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 here exists an independent system $S$ of equations of size $\Omega (n^{2})$, containing $n$ unknowns, which is such that $S$ causes only a defect effect of order $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 morphism $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.