While studying a bit of Joachim Lambek's calculus and some other applications of formal languages to the study of the structure of human language, I have come accross a reference to what authors like André Lentin has developed for the study of word combinations, namely, the so-called equations on the free monoid.
Could anyone explain me what those equations on the free monoid are?
Best regards and thanks in advance.
You can find the definition and a presentation of the main results in the Wikipedia entry Équation entre mots which apparently has not been translated in any other language.
Let $A$ be a finite set of constants and let $\Xi$ be a finite set of variables. A word equation is a pair $(u, v)$ of words of $(A \cup \Xi)^*$. A solution is a map $f:\Xi \to A^*$, which extends uniquely to a monoid homomorphism from $(A \cup \Xi)^*$ to $A^*$, such that $f(u) = f(v)$.
Quoting Wikipedia, the map $f(T) = bab$, $f(X) = abb$, $f(Y) = ab$, $f(Z) = ba$ is a solution of the equation $$ XaTZaT=YZbXaabY $$ since $(abb)a(bab)(ba)a(bab) = (ab)(ba)b(abb)aab(ab)$.
Makanin's theorem states that deciding whether a given equation has a solution is decidable.