A word equation is a tuple (α, β), usually written α = β, such that α and β are words over a combined alphabet X∪∑ consisting of variables X = {x, y, z, … } and terminal symbols ∑ = {a, b,...}. A solution to a word equation is a substitution of the variables for words in ∑* unifying the two terms α and β. In other words, a solution is a (homo)morphism h:(X∪∑)*→∑* satisfying h(a) = a for all a∈∑ such that h(α) = h(β). For example, one solution h to the word equation xaby = ybax is given by h(ⅹ) = b and h(y) = bab.
展开▼
