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 (cf. \Sigma ) and unknowns (cf. \Xi ).
≈ 10 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 (cf. \Sigma ) and unknowns (cf. \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.
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 primitive terminal word. It is well-known that the solutions of the commutation equation are exactly those assignments 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 assignments 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.…
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 (cf. \Sigma ) and unknowns (cf. \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.
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 primitive terminal word. It is well-known that the solutions of the commutation equation are exactly those assignments 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 assignments 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 (cf. below) terminates. word equations in one unknown, which can be checked for their solubility in linear time.
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. . 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^2y^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^2w_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_xw_y^2w_x . Now a length argument permits for the midpoint of each side to be identified here, and it follows from this observation that w_xw_y=z'=w_yw_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|\ge|w_z|+|w_x|\ge|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.
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)| , 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. 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.
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 products of |X|-r words, where r\ge 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 there 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 .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1362000376 under CC BY-SA 4.0; modifications have been made.